Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at Asana

Return the inorder traversal of a binary tree. Asana asks this to confirm you can implement both recursive and iterative tree walks — they care because the iterative pattern is what powers their cycle-free dependency walker.

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

Source citations

Public interview reports confirming this problem appears in Asana loops.

  • Glassdoor (2026-Q1)— Tree warmup before harder graph problems at Asana.

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values. Follow up: Recursive solution is trivial, could you do it iteratively?

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

Inorder is left -> visit -> right; call recursively on each subtree.

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

Tradeoff: Clean, but uses O(h) recursion stack. Stack-overflow risk on skewed trees.

2. Iterative with explicit stack

Push lefts onto a stack, then pop-visit-go-right.

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: Same O(h) space but explicit, so no stack overflow on huge skewed trees. The iterative form is what Asana grades on.

Asana-specific tips

At Asana, the follow-up to iterative is always Morris traversal (O(1) space). Even if you can't code Morris, mentioning that it threads links into right-null pointers to avoid the stack is bonus signal. Tie it to their internal need for stack-safe tree walks over million-task workspaces.

Common mistakes

  • Pushing both left and right onto the stack at once (that's preorder, not inorder).
  • Visiting the node before exhausting its left subtree.
  • Forgetting the inner while loop that drains all lefts.

Follow-up questions

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

  • Preorder (LC 144) and postorder (LC 145) iterative.
  • Morris traversal — O(1) space.
  • Validate that a tree is a valid BST using inorder (LC 98).

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 drain all lefts before popping?

Inorder visits the leftmost node first. The inner while loop walks to the leftmost node in the current subtree before any visit.

When does Morris beat the stack version?

When O(h) recursion stack would overflow on very deep trees and you genuinely need O(1) space. The tradeoff is temporary tree mutation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →