Skip to main content

9. Binary Tree Inorder Traversal

easyAsked at ServiceNow

Return the inorder traversal of a binary tree's node values. ServiceNow asks this to confirm recursion fluency and to see if you can write the iterative stack-based version — the same trick they use when walking approval-chain trees in their workflow engine.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2026-Q1)— ServiceNow loops use inorder traversal as a recursion-vs-iteration probe.
  • Reddit r/cscareerquestions (2025-11)— Reported with explicit ask for the iterative variant on a ServiceNow loop.

Problem

Given the root of a binary tree, return the inorder traversal of its node values. Inorder means: visit left subtree, then root, then 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. Recursion

Recurse left, push value, recurse right.

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

Tradeoff: Clean and obvious. The 'too easy' version — interviewer will follow up asking for iterative.

2. Iterative with explicit stack

Push lefts until null. Pop, emit, then move to the right child and repeat the push-lefts dance.

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 time and space as recursion, but the stack is explicit. ServiceNow workflow engines rely on this exact pattern for non-recursive tree walks because Glide-script call stacks are shallow.

ServiceNow-specific tips

ServiceNow grades for both versions — they'll ask the recursive one first, then 'now do it iteratively' to test stack-handling. Bonus signal: explain that the inner while-loop is the iterative analog of the 'recurse left' step, and the outer pop is the 'visit then recurse right' step.

Common mistakes

  • Confusing the order — preorder pushes root before left, postorder is different again.
  • Forgetting to handle the empty tree (root = null).
  • Trying to use a queue (BFS) instead of a stack (DFS).

Follow-up questions

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

  • Preorder (LC 144) and postorder (LC 145) traversals.
  • Morris traversal — O(1) space using leaf-pointer threading.
  • Inorder Successor in BST (LC 285).

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 this in O(1) space?

Yes — Morris traversal threads leaf pointers to predecessors. The trick is restoring the tree to original shape after the walk. Mention it as the follow-up.

Why is iterative considered harder?

Because you're simulating the implicit call stack with an explicit one, and you have to track 'where am I in the recursion' manually. The push-lefts pattern encodes that.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →