Skip to main content

14. Binary Tree Inorder Traversal

easyAsked at Notion

Visit every node in a binary tree left-root-right — the same traversal order Notion's block engine uses to render nested page content, making this a direct window into how interviewers think about document structure.

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

Problem

Given the root of a binary tree, return the inorder traversal of its node values (left subtree → root → right subtree).

Constraints

  • 0 <= number of nodes <= 100
  • -100 <= Node.val <= 100

Examples

Example 1

Input
root = [1,null,2,3]
Output
[1,3,2]

Explanation: Node 1 (no left) → node 1 itself → right subtree [2 with left child 3]: 1, 3, 2.

Example 2

Input
root = []
Output
[]

Approaches

1. Recursive DFS

Recurse left, collect root, recurse right — clean and mirrors the definition.

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

Tradeoff:

2. Iterative with explicit stack

Push nodes onto a stack while going left; on backtrack, visit and pivot right — O(1) space overhead per call frame, avoids call-stack depth limits for deep trees.

Time
O(n)
Space
O(h)
function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }
  return result;
}

Tradeoff:

Notion-specific tips

Notion engineers reason about nested blocks as trees daily. They want to see you articulate traversal order out loud and explain why the iterative version avoids stack-overflow on deeply nested pages — a real constraint in a document editor.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →