Skip to main content

94. Binary Tree Inorder Traversal

easy

Return the inorder traversal of a binary tree's node values. Recursion is one line; the iterative version with an explicit stack is the real interview test. Bonus points for Morris traversal in O(1) space.

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

Problem

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recursion is trivial: traverse(left), append node.val, traverse(right).

Hint 2

Iterative version: use a stack. Push all left children, pop and visit, then move to right.

Hint 3

Morris traversal achieves O(1) space by temporarily rewiring rightmost predecessors as threads, then restoring.

Solution approach

Reveal approach

Iterative with explicit stack: initialize stack = [] and curr = root and result = []. Loop while curr is not null or stack is non-empty: while curr is not null, push curr and move curr = curr.left (drain the left spine). Then pop the top, append its val to result, and set curr = popped.right. Return result. The stack holds the ancestor chain of the next node to visit. Recursive variant is straightforward. Morris traversal does it in O(1) extra space by making the rightmost node of each left subtree point back to its inorder successor temporarily.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • tree-dfs
  • stack
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Binary Tree Inorder Traversal and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →