Skip to main content

10. Binary Tree Inorder Traversal

easyAsked at Workday

Given the root of a binary tree, return the inorder traversal of its node values. Workday uses this to verify you can both recurse AND iterate trees — org charts may be too deep for recursion when traversing a 50,000-employee hierarchy.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE1 phone screen.
  • Blind (2026)— Workday tree-team interview.

Problem

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

Recurse left, visit, recurse right.

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

Tradeoff: Clean but O(h) stack — risky for skewed trees of 50k employees.

2. Iterative with explicit stack

Push left spine, pop+visit, then descend right.

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 iterative — no call-stack overflow on deep org charts. The 'push left spine then pop' pattern generalizes to LC 173 (BST iterator).

Workday-specific tips

Workday interviewers ALWAYS follow up with 'now do it iteratively' — they explicitly mention the org-chart depth motivation. Lead with iterative if you can; if not, show recursion then convert. The iterative version is also the basis of an O(1)-amortized BST iterator they'll ask next.

Common mistakes

  • Missing the inner while loop that pushes the entire left spine.
  • Visiting before pushing left children — gives preorder.
  • Forgetting to handle the empty-tree case.

Follow-up questions

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

  • Convert to Morris traversal (O(1) space).
  • Binary Tree Iterator (LC 173) — externalize this loop into next()/hasNext().
  • Preorder and Postorder iterative variants.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can I do it in O(1) space?

Yes — Morris traversal rewires right-pointers temporarily. Worth mentioning by name; coding it under time pressure is risky.

Why inorder specifically?

On a BST, inorder yields sorted values — useful for emitting an org chart sorted by hire date or employee ID.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →