Tree Traversal Patterns: Inorder, Preorder, Postorder, Level-Order, and Morris

Tree traversal is the foundation of almost every tree problem on LeetCode. Knowing when to use inorder vs preorder vs level-order — and how to implement each both recursively and iteratively — lets you solve most tree problems mechanically. This guide covers every traversal method with templates and problem solutions.

Tree Node Definition

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

// Java version
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

        1
     / \
    2   3
   / \   \
  4   5   6

Inorder   (L, Root, R): 4, 2, 5, 1, 3, 6
Preorder  (Root, L, R): 1, 2, 4, 5, 3, 6
Postorder (L, R, Root): 4, 5, 2, 6, 3, 1
Level-order:            1, 2, 3, 4, 5, 6

Inorder Traversal (Left, Root, Right)

Visits nodes in sorted order for BSTs. Use it when you need sorted values or need to process nodes in ascending order.

# Recursive
def inorderTraversal(root: TreeNode) -> list[int]:
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    
    dfs(root)
    return result

# Iterative (using explicit stack)
def inorderTraversal_iter(root: TreeNode) -> list[int]:
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        
        # Process node
        current = stack.pop()
        result.append(current.val)
        
        # Move to right subtree
        current = current.right
    
    return result

Kth Smallest Element in BST (LC 230)

def kthSmallest(root: TreeNode, k: int) -> int:
    stack = []
    current = root
    count = 0
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        
        current = current.right
    
    return -1

Validate BST (LC 98)

def isValidBST(root: TreeNode) -> bool:
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
    
    return validate(root)

Preorder Traversal (Root, Left, Right)

Visits the root before children. Use it when you need to process a node before its subtrees (e.g., copying a tree, serialization).

# Recursive
def preorderTraversal(root: TreeNode) -> list[int]:
    result = []
    
    def dfs(node):
        if not node:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return result

# Iterative
def preorderTraversal_iter(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Maximum Depth of Binary Tree (LC 104)

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Invert Binary Tree (LC 226)

def invertTree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

Postorder Traversal (Left, Right, Root)

Visits children before the root. Use it when you need to process subtrees before the parent (e.g., computing heights, deleting trees).

# Recursive
def postorderTraversal(root: TreeNode) -> list[int]:
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)
    
    dfs(root)
    return result

# Iterative (modified preorder, then reverse)
def postorderTraversal_iter(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]  # reverse gives postorder

Diameter of Binary Tree (LC 543)

def diameterOfBinaryTree(root: TreeNode) -> int:
    diameter = 0
    
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        diameter = max(diameter, left_h + right_h)
        return 1 + max(left_h, right_h)
    
    height(root)
    return diameter

Lowest Common Ancestor (LC 236)

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root     # p and q are on different sides
    return left or right  # both on the same side

Level-Order Traversal (BFS)

Visits all nodes at depth d before any node at depth d+1. Use it for level-by-level processing.

from collections import deque

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

// Java version
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Right Side View (LC 199)

def rightSideView(root: TreeNode) -> list[int]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)  # last node in level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

Morris Traversal (O(1) Space)

Morris traversal uses the tree’s null pointers to create temporary links, eliminating the need for a stack or recursion. Space complexity is O(1).

def morris_inorder(root: TreeNode) -> list[int]:
    result = []
    current = root
    
    while current:
        if not current.left:
            # No left subtree -- visit and go right
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor (rightmost in left subtree)
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                # Create thread: predecessor.right -> current
                predecessor.right = current
                current = current.left
            else:
                # Thread exists, we are back -- remove thread and visit
                predecessor.right = None
                result.append(current.val)
                current = current.right
    
    return result

Morris traversal modifies the tree temporarily but restores it completely. Each edge is visited at most twice, so the time complexity is O(n).

Choosing the Right Traversal

Key Takeaways

Inorder gives sorted order for BSTs. Preorder processes the root first, useful for serialization and tree construction. Postorder processes children first, essential for computing heights and bottom-up aggregation. Level-order uses BFS for level-by-level processing. Morris traversal achieves O(1) space by threading the tree. Most tree problems reduce to choosing the right traversal order and defining what to do at each node. Start with the recursive version, then convert to iterative if the problem requires it or if stack depth is a concern.