Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at PayPal

Return 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 Alex Chen, 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

Input
root = [1,null,2,3]
Output
[1,3,2]

Example 2

Input
root = []
Output
[]

Example 3

Input
root = [1]
Output
[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Binary Tree Inorder Traversal and other PayPal interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →