Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at GitLab

Return the in-order traversal of a binary tree's node values.

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

Problem

Given the root of a binary tree, return an array of node values produced by in-order (left, node, right) traversal.

Constraints

  • 0 <= nodes <= 100
  • -100 <= val <= 100

Examples

Example 1

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

Example 2

Input
root=[]
Output
[]

Approaches

1. Recursive

Recurse left, push value, recurse right.

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

Tradeoff:

2. Iterative with stack

Push lefts, pop, visit, then move to right.

Time
O(n)
Space
O(h)
function inorder(root){
  const out=[], st=[]; let n=root;
  while (n || st.length){
    while (n){ st.push(n); n=n.left; }
    n=st.pop(); out.push(n.val); n=n.right;
  }
  return out;
}

Tradeoff:

GitLab-specific tips

GitLab values explaining why the iterative version is preferable when traversing massive merge-request comment trees on a single runner.

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 GitLab interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →