Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at Adobe

Return the inorder traversal of a binary tree's node values. Adobe asks this to confirm you can convert between recursive and iterative tree traversals — the same flexibility you need when traversing nested SVG groups or PSD layer trees.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-Q1)— Adobe SDE-II screens use this to test iterative traversal.
  • LeetCode Discuss (2025-08)— Often paired with 'now make it iterative' follow-up.

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder means left subtree, root, right subtree.

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, push self, recurse right.

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

Tradeoff: Simple but stack-bounded. For deeply nested SVG/PSD trees (10k+ levels) you'd blow the call stack.

2. Iterative with explicit stack

Push left spine until null; then pop, record, descend right.

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: Same complexity but heap-allocated, so resilient to deep trees. Adobe will ask 'now write it iteratively' as a follow-up — be ready.

Adobe-specific tips

Adobe Creative Cloud apps deal with deeply nested document trees (layer groups, SVG groups, paragraph styles). They'll ask the iterative version because recursion can blow the stack on user content. Mention Morris traversal (O(1) space) as a bonus if you have time — it impresses systems-leaning interviewers.

Common mistakes

  • Mixing up the push order — preorder is 'self, left, right'; inorder is 'left, self, right'.
  • Forgetting to handle empty tree.
  • In iterative version, descending into right BEFORE popping — produces wrong order.

Follow-up questions

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

  • Preorder traversal (LC 144).
  • Postorder traversal (LC 145) — trickier iteratively.
  • Morris traversal — O(1) space using threaded tree.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

When is iterative strictly better?

When the tree might be skewed deep (a left-only chain). A 50,000-node skewed tree will overflow most language runtimes' call stacks. The explicit stack on the heap survives.

What's Morris traversal?

A technique that temporarily mutates the tree (adds a thread from a predecessor's right child to the current node), achieving O(1) extra space. Restores the tree on the second visit. Worth mentioning but only implement if asked.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →