10. Binary Tree Inorder Traversal
easyAsked at DatabricksReturn 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 Sam K., 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
root = [1,null,2,3][1,3,2]Example 2
root = [][]Example 3
root = [1][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.
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.