Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at Plaid

Return the inorder traversal of a binary tree's node values. Plaid asks this as a tree-recursion baseline before harder traversal problems on transaction-category hierarchies.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid OA warm-up before a category-tree follow-up.
  • Glassdoor (2025)— Plaid SWE I screen.

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
[]

Approaches

1. Recursive

Recurse left, append node, recurse right.

Time
O(n)
Space
O(h) recursion stack
function inorderTraversal(root) {
  const out = [];
  function go(n) {
    if (!n) return;
    go(n.left);
    out.push(n.val);
    go(n.right);
  }
  go(root);
  return out;
}

Tradeoff: Simple. Risk of stack overflow on skewed trees with > 10^4 nodes, but the LC bound is 100.

2. Iterative with explicit stack

Push left spine, pop and visit, then jump to right child's left spine.

Time
O(n)
Space
O(h)
function inorderTraversal(root) {
  const out = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}

Tradeoff: Avoids stack-overflow on deep trees. The two nested loops mirror the recursive structure exactly.

Plaid-specific tips

Plaid often follows up with 'what if the tree is a category hierarchy with 10M nodes' — be ready to switch to iterative. Bonus signal: mention Morris traversal (O(1) space) as a curiosity, but only ship it if explicitly asked — it mutates the tree temporarily and is overkill for the base problem.

Common mistakes

  • Forgetting to handle null root.
  • Visiting node before recursing left — that's preorder, not inorder.
  • Mixing up the iterative pattern — pushing all nodes onto the stack at once instead of walking the left spine.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Preorder and postorder iterative versions.
  • Inorder on a BST — confirm output is sorted.
  • Morris traversal — O(1) extra space by threading the tree.

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 does inorder on a BST give a sorted list?

By definition: left subtree < node < right subtree, and we visit them in that order. Plaid uses this fact to convert a BST-keyed merchant tree into a sorted display list in O(n).

When does the recursive version fail?

Stack overflow on skewed trees of depth ~10^4 in V8. The LC bound is 100 so it's safe; production code that ingests bank category hierarchies should default to iterative.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →