Skip to main content

10. Binary Tree Inorder Traversal

easyAsked at Databricks

Return the inorder traversal of a binary tree's nodes' values. Databricks asks this to see if you can write both the recursive and iterative versions and explain why the iterative one matters in JVM-stack-bounded environments.

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Blind (2025-09)— Databricks Catalyst optimizer team — used to test recursion + explicit-stack fluency.
  • Glassdoor (2026-Q1)— Often asked alongside expression-tree visitor question.

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder = left, node, right.

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

DFS — recurse left, visit node, recurse right.

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

Tradeoff: Clean and clear. Use unless interviewer specifies iterative.

2. Iterative with explicit stack

Walk left, pushing nodes. Pop, visit, then traverse right subtree.

Time
O(n)
Space
O(h)
function inorderTraversal(root) {
  const out = [], 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 recursion-depth limits. Critical at Databricks for JVM-stack-bounded environments and Spark executors.

Databricks-specific tips

Databricks engineers care about iterative tree traversal because Catalyst's tree visitor cannot risk JVM stack overflow on a deeply-nested query plan. Volunteer the iterative version even if not asked, and articulate the JVM-stack-overflow risk. The bonus signal is explaining that Morris traversal would give O(1) space if you're allowed to mutate the tree.

Common mistakes

  • Returning during the recursion (e.g., `return dfs(...)`) instead of building an output list.
  • Forgetting the inner 'walk left' while-loop in the iterative version.
  • Confusing inorder with preorder — left/node/right not node/left/right.

Follow-up questions

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

  • Iterative pre/postorder.
  • Morris traversal — O(1) extra space using threaded links.
  • Catalyst-style visitor: how would you traverse a query plan of depth 10,000?

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 is iterative worth knowing?

JVM stack overflows on deep recursion. For trees that are nearly linked-list-shaped (depth = n), the recursive version dies; the iterative version uses heap-allocated stack and is bounded only by available memory.

What is Morris traversal?

An O(1)-space traversal that temporarily mutates the tree to create threaded links from rightmost-of-left-subtree back to the node, then undoes them on the way down. Worth mentioning but rarely required.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →