9. Binary Tree Inorder Traversal
easyAsked at PayPalReturn the inorder (left, root, right) traversal of a binary tree's nodes. PayPal asks this to test stack-based iterative thinking — the same scaffolding used to walk a transaction-tree where parent transactions point at children (settlement → captures → auths).
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in PayPal loops.
- Glassdoor (2026-Q1)— PayPal SDE-1, asked for both recursive and iterative solutions.
Problem
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Constraints
The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100
Examples
Example 1
root = [1,null,2,3][1,3,2]Example 2
root = [][]Example 3
root = [1][1]Approaches
1. Recursive
Walk left, visit root, walk right. Append into a shared array.
- Time
- O(n)
- Space
- O(h) recursion stack
function inorderTraversal(root) {
const out = [];
function dfs(node) {
if (!node) return;
dfs(node.left);
out.push(node.val);
dfs(node.right);
}
dfs(root);
return out;
}Tradeoff: Clean but uses recursion stack. PayPal interviewers often follow up with 'now iterative please.'
2. Iterative with explicit stack (optimal)
Push left spine onto a stack. Pop, visit, then descend the popped node's right child's left spine.
- Time
- O(n)
- Space
- O(h)
function inorderTraversal(root) {
const out = [];
const stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
out.push(curr.val);
curr = curr.right;
}
return out;
}Tradeoff: Explicit stack avoids recursion-depth risk on skewed trees. PayPal interviewers see this as a maturity signal.
PayPal-specific tips
PayPal expects you to know both forms. The follow-up is typically Morris traversal (O(1) space) — mention it even if you don't code it. Bonus signal: relate the iterative pattern to a transaction audit trail walk where you don't want the JVM stack to blow up on a 100k-deep settlement chain.
Common mistakes
- Visiting in pre-order or post-order accidentally — order is left, root, right.
- Pushing a node twice — the iterative version pushes each node exactly once on the descent.
- Forgetting to descend curr.right after popping — turns into a partial traversal.
Follow-up questions
An interviewer at PayPal may pivot to one of these next:
- Pre-order and post-order iterative (LC 144, LC 145).
- Morris inorder traversal in O(1) space.
- Validate BST using inorder (LC 98) — inorder of BST must be strictly increasing.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why descend left first?
Inorder = left, root, right. You push roots as you descend left; when you can't go further left, the top of the stack is the leftmost unvisited node.
Recursive vs iterative — which is preferred?
Recursive is cleaner; iterative is safer on deep trees. Production code at PayPal scale tends to use iterative for the depth guarantee.