Binary Tree Inorder Traversal

Difficulty: Easy | Acceptance: 80.00% | Paid: No Topics: Stack, Tree, Depth-First Search, Binary Tree

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Table of Contents

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Depth-First Search using Stack
• Morris Traversal

Examples

Example 1

Input:

root = [1,null,2,3]

Output:

[1,3,2]

Example 2

Input:

root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output:

[4,2,6,5,7,1,3,9,8]

Example 3

Input:

root = []

Output:

[]

Example 4

Input:

root = [1]

Output:

[1]

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Recursive Depth-First Search

Intuition Inorder traversal follows the Left-Root-Right pattern. Recursion naturally mimics this by calling the function on the left child, processing the current node, and then calling on the right child.

Steps

• Check if the current node is null. If so, return.
• Recursively call the traversal function on the left subtree.
• Append the current node’s value to the result list.
• Recursively call the traversal function on the right subtree.

# Definition for a binary tree node.
# 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]:
        res = []
        
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            res.append(node.val)
            dfs(node.right)
            
        dfs(root)
        return res

Complexity

• Time: O(n) — We visit every node exactly once.
• Space: O(h) — Where h is the height of the tree. This is the space used by the recursion stack. In the worst case (skewed tree), h is n. In the best case (balanced tree), h is log n.
• Notes: Simple and readable, but may cause a stack overflow for extremely deep trees.

Iterative Depth-First Search using Stack

Intuition We can simulate the recursive call stack explicitly using a data structure. We traverse as far left as possible, pushing nodes onto the stack. When we can’t go left anymore, we pop a node, process it, and then move to its right child.

Steps

• Initialize an empty stack and a pointer curr to the root.
• While curr is not null or the stack is not empty:
  • While curr is not null, push curr to the stack and move curr to curr.left.
  • Pop the top node from the stack and add its value to the result.
  • Set curr to the right child of the popped node (curr.right).

# Definition for a binary tree node.
# 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]:
        res = []
        stack = []
        curr = root
        
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            res.append(curr.val)
            curr = curr.right
            
        return res

Complexity

• Time: O(n) — Each node is pushed and popped from the stack exactly once.
• Space: O(h) — The stack stores at most h nodes, where h is the height of the tree.
• Notes: Avoids recursion stack overflow risks but requires managing the stack manually.

Morris Traversal

Intuition Morris Traversal allows us to traverse the tree in O(1) extra space (excluding the output list) by temporarily modifying the tree structure. We create “threads” (links) from the rightmost node of a left subtree back to its parent (current node). This allows us to return to the parent after finishing the left subtree without using a stack.

Steps

• Initialize curr to root.
• While curr is not null:
  • If curr has no left child:
    • Add curr.val to result.
    • Move curr to curr.right.
  • If curr has a left child:
    • Find the rightmost node in the left subtree (predecessor).
    • If the predecessor’s right child is null:
      • Link it to curr (predecessor.right = curr).
      • Move curr to curr.left.
    • If the predecessor’s right child is curr (thread already exists):
      • Remove the thread (predecessor.right = null).
      • Add curr.val to result.
      • Move curr to curr.right.

# Definition for a binary tree node.
# 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]:
        res = []
        curr = root
        
        while curr:
            if not curr.left:
                res.append(curr.val)
                curr = curr.right
            else:
                pre = curr.left
                while pre.right and pre.right != curr:
                    pre = pre.right
                
                if not pre.right:
                    pre.right = curr
                    curr = curr.left
                else:
                    pre.right = None
                    res.append(curr.val)
                    curr = curr.right
                    
        return res

Complexity

• Time: O(n) — Each edge is traversed at most twice (once to establish thread, once to remove it).
• Space: O(1) — We only use a few pointers for traversal. The output list is not counted towards auxiliary space.
• Notes: Modifies the tree structure temporarily (though restores it). Useful in memory-constrained environments.