Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at Salesforce

Return the inorder traversal of a binary tree. Salesforce uses this to test both recursive and iterative tree traversal, since their org-hierarchy queries (e.g., role hierarchy) rely on tree walks.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce role-hierarchy team uses tree walks as a daily pattern.
  • LeetCode Discuss (2025)— Iterative variant is a Salesforce favorite to test stack management.

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

Time
O(n)
Space
O(h) recursion stack
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: Clean and obvious. Acceptable but Salesforce often asks for the iterative version as a follow-up.

2. Iterative with explicit stack

Push lefts onto the stack until null. Pop, visit, then move to right and repeat.

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

Tradeoff: Iterative avoids stack-overflow on skewed trees. The inner while-loop simulates the recursion frame.

Salesforce-specific tips

Salesforce role-hierarchy traversal uses this exact pattern, and they value candidates who can switch between recursive and iterative on demand. Bonus signal: mention that inorder on a BST gives sorted output, which is the basis of their indexed-range queries.

Common mistakes

  • Returning inside the recursion instead of pushing to a closure result — breaks the contract.
  • In the iterative version, forgetting to advance to cur.right after popping — infinite loop on the same node.
  • Confusing inorder with preorder or postorder — Salesforce will test the distinction.

Follow-up questions

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

  • Preorder and postorder traversals (iterative).
  • Morris traversal — O(1) space using tree threading.
  • Validate BST (LC 98 — uses inorder).

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 would I prefer iterative over recursive?

When the tree depth might exceed the call stack (skewed trees, 10K+ nodes) or when you need to pause/resume traversal for streaming.

What's Morris traversal?

An O(1)-space variant that temporarily threads predecessor pointers to siblings. Rarely needed but Salesforce sometimes asks as a stretch.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →