Skip to main content

10. Binary Tree Inorder Traversal

easyAsked at Palantir

Return the inorder traversal of a binary tree's values. Palantir asks this to test whether you can write iterative tree traversal — a primitive for walking ontology graphs without stack overflow on deep hierarchies.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2025-11)— Palantir FDE asked for both recursive and iterative versions.
  • Blind (2026-Q1)— Used to set up Morris traversal as a follow-up.

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

Recurse left, append value, recurse right.

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

Tradeoff: Simplest. Risk: stack overflow on skewed trees of depth >10k.

2. Iterative with explicit stack

Push lefts, pop and emit, then descend right.

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

Tradeoff: Same time, but uses heap memory for the stack so it survives deep trees. Crucial for production code over arbitrary user data.

Palantir-specific tips

Palantir interviewers expect you to write both versions and to articulate why the iterative one matters in production: a user-defined ontology can have arbitrarily deep parent chains, and recursive traversal will stack-overflow. Bonus signal: mention Morris traversal (O(1) extra space using right-pointer threading) but don't code it unless asked — they're testing fluency, not memorization.

Common mistakes

  • Mixing up the order — preorder appends BEFORE recursing left.
  • Pushing root.right first in iterative version — that's preorder, not inorder.
  • Forgetting the outer while condition needs both curr AND stack.

Follow-up questions

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

  • Preorder and postorder iterative variants.
  • Morris traversal — O(1) extra space.
  • Recover BST (LC 99) — uses inorder to find swapped nodes.

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 does inorder traversal of a BST produce a sorted sequence?

Because the BST invariant says left < node < right. Inorder visits left subtree first (smaller), then the node, then right subtree (larger) — which is exactly the sort order.

What's Morris traversal?

A technique that temporarily threads the rightmost node of each left subtree to point to its inorder successor. No explicit stack, O(1) extra space, but modifies the tree during traversal (restores it before returning).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →