Skip to main content

10. Binary Tree Inorder Traversal

easyAsked at Reddit

Return the inorder traversal of a binary tree. Reddit asks this to test recursive vs. iterative fluency — the same primitive used to flatten their nested comment trees into linear render lists.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit comments-team phone screen.
  • LeetCode Discuss (2025-10)— Cited as the canonical tree warm-up before comment-tree flattening follow-ups.

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values. Follow up: can 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

Recurse left, visit, recurse right.

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

Tradeoff: Cleanest. Stack-overflows on very deep trees (>10k nodes in JS).

2. Iterative with explicit stack (optimal for deep trees)

Push lefts onto a stack until null. Pop, visit, then move to right child and repeat.

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: Heap-allocated stack instead of call stack. Survives 10^5+ depth that would blow recursion.

Reddit-specific tips

Reddit interviewers want both versions. Bonus signal: explicitly mention that comment threads can nest 20+ levels deep on hot posts and that an iterative DFS is required for production rendering. Mention Morris traversal (O(1) space) if asked.

Common mistakes

  • Forgetting the inner while (cur) loop and only pushing root.
  • Pushing the right child immediately instead of after pop.
  • Returning the recursion call value (it's void).

Follow-up questions

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

  • Preorder traversal (LC 144).
  • Postorder traversal (LC 145) — two-stack trick.
  • Morris traversal for O(1) space — uses tree itself as a stack.

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 inorder specifically?

For a BST, inorder visits values in sorted order. Reddit's BST-of-vote-events relies on this.

When would recursion fail in production?

Reddit's longest threads (e.g., the /r/iAmA Obama AMA) had hundreds of nesting levels. Recursive DFS in Python/JS would stack-overflow.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →