Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at Snowflake

Return the in-order traversal of a binary tree. Snowflake asks this to test whether you can produce both the recursive and the iterative-with-stack solution — relevant because their B-tree-style indexes use ordered iteration for range scans.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake storage-team screens use this to set up B-tree range-scan follow-up.
  • Blind (2025-10)— Asked at Snowflake new-grad onsite.

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 (warm-up)

Recurse left, visit, recurse right.

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

Tradeoff: Trivial but uses recursion stack. Fine for balanced trees, blows up on skewed.

2. Iterative with explicit stack (optimal)

Push left spine onto stack. Pop, visit, then descend the right child's left spine. Repeat.

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

Tradeoff: Same complexity, but uses a heap-allocated stack — survives skewed trees that would overflow the recursion stack. This is the form a B-tree range iterator takes.

Snowflake-specific tips

Snowflake interviewers will ask both versions and follow up on stack-overflow risk for deep trees. Bonus signal: pivot to Morris traversal (O(1) space using threaded right pointers) and discuss why an index iterator wouldn't want to mutate the tree — your iterator should be read-only.

Common mistakes

  • Visiting before recursing left — that's pre-order, not in-order.
  • In the iterative version, popping before pushing the full left spine — gets the order wrong.
  • Setting curr = null at the wrong spot and exiting the loop early.

Follow-up questions

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

  • Morris traversal (O(1) space).
  • Iterative pre-order and post-order.
  • How does Snowflake's B-tree range scan iterate ordered keys?

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 iterative if recursion is shorter?

Recursion depth equals tree height. A 10000-node skewed tree blows the JS engine's stack. Iterative uses heap memory and survives.

Why is in-order the natural one for range scans?

In-order traversal of a BST yields keys in sorted order, which is exactly what a range scan needs. A B-tree index does the same iteration shape against on-disk pages.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →