Skip to main content

94. Binary Tree Inorder Traversal

easyAsked at Netflix

Given the root of a binary tree, return the inorder traversal of its node values. Netflix asks this not for the recursion (everyone gets that) but for the explicit-stack and Morris-traversal follow-ups that signal real tree fluency.

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

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix phone-screen reports list this as the warmup before harder tree problems on the same screen.
  • Blind (2025-09)— Netflix SWE writeups consistently mention the iterative-stack version as the expected variant for senior loops.

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 (warmup)

Recursively traverse left, push root.val, then traverse right.

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

Tradeoff: Trivial — everyone gets this. Mention it then immediately move to iterative because the interviewer is probably going to ask anyway.

2. Iterative with explicit stack (the interview answer)

Use a stack to simulate the recursion. Walk left as far as possible, pushing each node; then pop, output, and move to the right subtree.

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: Same O(n) time but the iterative version uses an explicit stack instead of the call stack. This is the version most Netflix interviewers want — recursion proves you can't blow the stack on deep trees.

3. Morris traversal (the follow-up answer)

For each node, temporarily thread the rightmost node of its left subtree to point back to the node, then traverse via these threads — O(1) extra space.

Time
O(n)
Space
O(1)
function inorderMorris(root) {
  const out = [];
  let cur = root;
  while (cur) {
    if (!cur.left) { out.push(cur.val); cur = cur.right; }
    else {
      let pred = cur.left;
      while (pred.right && pred.right !== cur) pred = pred.right;
      if (!pred.right) { pred.right = cur; cur = cur.left; }
      else { pred.right = null; out.push(cur.val); cur = cur.right; }
    }
  }
  return out;
}

Tradeoff: O(1) extra space — the only constant-space inorder traversal. Modifies tree pointers temporarily but restores them, so the final tree is unchanged. Worth knowing for the follow-up; don't lead with it.

Netflix-specific tips

Netflix interviewers will accept the recursive version as a warmup but the real signal is whether you can transition to iterative without prompting. Say something like: 'For senior code I'd write the iterative version to avoid stack-depth issues on deep trees.' If they ask for O(1) extra space, that's the Morris follow-up — explicitly call out that you're temporarily threading the tree and will restore it.

Common mistakes

  • In the iterative version, popping before walking all the way left — gives a partial preorder, not inorder.
  • Initializing cur = root.left instead of root — misses the root's leftmost branch.
  • In Morris, forgetting to restore pred.right = null in the second branch — leaves the tree mutated.

Follow-up questions

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

  • Preorder Traversal (LC 144) and Postorder Traversal (LC 145) — same iterative pattern variants.
  • Construct Binary Tree from Inorder + Preorder/Postorder.
  • Validate Binary Search Tree (LC 98) — inorder of a BST must be strictly increasing.

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 preferred over recursive in production?

Because recursive blows the call stack on deeply skewed trees (e.g., a tree shaped like a linked list with n = 10^5 nodes). The explicit stack version uses heap memory and won't crash.

Is Morris traversal worth practicing?

Yes for senior loops at companies that probe O(1) extra space. It's tricky to get right under pressure — practice the threading-and-unthreading state machine until it feels mechanical.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →