DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Binary Tree Inorder Traversal

easyTreesAWS Cloud Support

Problem statement

Given the root of a binary tree, return the values of its nodes in in-order: for every node, first everything in its left subtree, then the node itself, then everything in its right subtree.

For a binary search tree, in-order visits the values in ascending order. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [4, 2, 6, 1, 3, 5]

Output: [1, 2, 3, 4, 5, 6]

Example 2

Input: root = [7, null, 8, 9]

Output: [7, 9, 8]

Explanation: 7 has no left child, so it comes first. Then 8's subtree: its left child 9, then 8.

Hints

Approach

Morris traversal gets rid of the stack. The only reason a stack is needed is to find the way back up to a node after finishing its left subtree. Morris stores that way back inside the tree itself: before going left, it makes the rightmost node of the left subtree (the node's in-order predecessor) point back to the node through its empty right pointer.

  1. If cur has no left child, record it and move right.
  2. Otherwise, find the predecessor: go left once, then right as far as possible (stopping if you reach cur).
  3. If the predecessor's right is empty, point it at cur and move cur left.
  4. If it already points at cur, the left subtree is done: remove the link, record cur, and move right.

Every temporary link is removed on the second visit, so the tree is unchanged at the end. Each edge is walked at most a few times, so the time is still linear.

ComplexityTime O(n)Space O(1) besides the output
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional["TreeNode"]) -> list[int]:
out = []
cur = root
while cur:
if cur.left is None:
out.append(cur.val)
cur = cur.right
continue
pred = cur.left # rightmost node of the left subtree
while pred.right and pred.right is not cur:
pred = pred.right
if pred.right is None:
pred.right = cur # temporary link back up
cur = cur.left
else:
pred.right = None # left side done: remove the link
out.append(cur.val)
cur = cur.right
return out

Follow-up questions

  • Write pre-order and post-order traversals iteratively.
  • Build a BST iterator with next() and hasNext() that uses O(h) memory.

Frequently asked questions

It temporarily modifies the tree, so it is not safe if another thread reads the tree at the same time, and an exception mid-walk could leave links behind. In interviews it is a good answer to "can you do it in O(1) space?"; in production the stack version is usually preferred.

Pre-order records the node before its subtrees, post-order after both. Pre-order is what you use to copy or serialise a tree; post-order is what you use when a node needs its children's results first, such as computing sizes or deleting a directory tree.

Traversal order is the core of walking any hierarchy: listing a directory tree, evaluating nested config, or tearing down resources children-first. Being able to switch between recursion and an explicit stack is also practical, since deep hierarchies can exceed recursion limits.