Tree Traversal Patterns 2026: BFS, DFS, Views, LCA [20+ Problems]

Last Updated: June 2026

Why Tree Traversal is a Core Interview Topic

Candidates report tree questions in roughly 20-25% of all coding interview rounds, based on public preparation resources and candidate-reported interview accounts from 2025 to 2026. Every tree problem, regardless of surface form, reduces to one of six traversal patterns: DFS inorder/preorder/postorder, BFS level-order, or specialized algorithms like LCA and Morris traversal.

Master these patterns and you can decode any tree problem in under 60 seconds.

Tree Node Definition

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

Pattern 1: DFS Traversals (Recursive)

def inorder(root):
    """Left -> Root -> Right. BST inorder = sorted."""
    if not root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

def preorder(root):
    """Root -> Left -> Right. Used to copy/serialize tree."""
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

def postorder(root):
    """Left -> Right -> Root. Used to delete tree, evaluate expressions."""
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

When to use each:

Pattern 2: Iterative DFS (Stack-Based)

def inorder_iterative(root):
    """
    Simulate call stack explicitly. Avoids recursion limit issues.
    Time: O(n)  Space: O(h)
    """
    result = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result


def preorder_iterative(root):
    """
    Push right then left so left is processed first.
    Time: O(n)  Space: O(h)
    """
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Pattern 3: BFS / Level-Order Traversal

from collections import deque

def level_order(root):
    """
    Process tree level by level.
    Time: O(n)  Space: O(w) where w = max width
    """
    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

Practice Problems

Problem 1: Binary Tree Level Order Traversal

Asked at: Amazon, Google, Microsoft, Facebook

def level_order_traversal(root):
    """Same as template above. Return list of lists."""
    return level_order(root)

# Example: Tree [3,9,20,null,null,15,7]
# Output: [[3],[9,20],[15,7]]

Complexity: Time O(n), Space O(n)

Problem 2: Binary Tree Zigzag Level Order Traversal

Asked at: Amazon, Google, Microsoft

def zigzag_level_order(root):
    """
    Alternate direction each level. Use deque with appendleft/append.
    Time: O(n)  Space: O(n)
    """
    if not root:
        return []

    result = []
    queue = deque([root])
    left_to_right = True

    while queue:
        level_size = len(queue)
        level = deque()

        for _ in range(level_size):
            node = queue.popleft()

            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(list(level))
        left_to_right = not left_to_right

    return result

Complexity: Time O(n), Space O(n)

Problem 3: Binary Tree Right Side View

Asked at: Amazon, Facebook, Bloomberg

def right_side_view(root):
    """
    Level-order: take last element of each level.
    Time: O(n)  Space: O(n)
    """
    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)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result

# Example: [1,2,3,null,5,null,4] -> [1,3,4]

Complexity: Time O(n), Space O(n)

Problem 4: Maximum Depth of Binary Tree

Asked at: Amazon, Google, TCS, Infosys

def max_depth(root):
    """
    DFS: height = 1 + max(height(left), height(right)).
    Time: O(n)  Space: O(h)
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Iterative BFS approach
def max_depth_bfs(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

Complexity: Time O(n), Space O(h)

Problem 5: Diameter of Binary Tree

Asked at: Amazon, Google, Facebook, Microsoft

def diameter_of_binary_tree(root):
    """
    Diameter through node = left_height + right_height.
    Track max diameter globally. Return height from each recursive call.
    Time: O(n)  Space: O(h)
    """
    max_d = [0]

    def height(node):
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        max_d[0] = max(max_d[0], lh + rh)
        return 1 + max(lh, rh)

    height(root)
    return max_d[0]

Complexity: Time O(n), Space O(h)

Problem 6: Lowest Common Ancestor (LCA) - Binary Tree

Asked at: Amazon, Google, Microsoft, Facebook - very frequently asked

def lca(root, p, q):
    """
    If current node is p or q: return it.
    If both subtrees return non-null: current node is LCA.
    If only one returns non-null: propagate that result.
    Time: O(n)  Space: O(h)
    """
    if not root or root == p or root == q:
        return root

    left = lca(root.left, p, q)
    right = lca(root.right, p, q)

    if left and right:
        return root    # p in one subtree, q in other
    return left or right

# Example: LCA of nodes 2 and 8 in BST [6,2,8,0,4,7,9] = 6

Complexity: Time O(n), Space O(h)

Problem 7: LCA in Binary Search Tree

Asked at: Amazon, Google, Microsoft

def lca_bst(root, p, q):
    """
    Use BST property: if both p and q < root.val, go left.
    If both > root.val, go right. Otherwise, root is LCA.
    Time: O(h) = O(log n) for balanced BST  Space: O(1) iterative
    """
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

Complexity: Time O(h), Space O(1)

Problem 8: Validate Binary Search Tree

Asked at: Amazon, Google, Microsoft

def is_valid_bst(root):
    """
    DFS with min/max bounds. Each node must be in (min_val, max_val).
    Time: O(n)  Space: O(h)
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        if not (min_val < node.val < max_val):
            return False
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))

Complexity: Time O(n), Space O(h)

Problem 9: Symmetric Tree

Asked at: Amazon, Microsoft, TCS

def is_symmetric(root):
    """
    Mirror check: left subtree mirrored against right subtree.
    Time: O(n)  Space: O(h)
    """
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

Complexity: Time O(n), Space O(h)

Problem 10: Binary Tree Maximum Path Sum

Asked at: Google, Amazon, Facebook, Microsoft - hard but high frequency

def max_path_sum(root):
    """
    At each node: max contribution = node.val + max(0, left_gain, right_gain).
    Path through node = left_gain + node.val + right_gain.
    Time: O(n)  Space: O(h)
    """
    max_sum = [float('-inf')]

    def max_gain(node):
        if not node:
            return 0

        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # Path going through this node
        price_through_node = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], price_through_node)

        # Return max gain if we continue from this node (can't split)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum[0]

Complexity: Time O(n), Space O(h)

Problem 11: Serialize and Deserialize Binary Tree

Asked at: Google, Amazon, Facebook, Microsoft - asked in system design rounds too

def serialize(root):
    """Preorder DFS. Null nodes = '#'."""
    if not root:
        return '#'
    return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)


def deserialize(data):
    """
    Rebuild from preorder string.
    Time: O(n)  Space: O(n)
    """
    nodes = iter(data.split(','))

    def build():
        val = next(nodes)
        if val == '#':
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node

    return build()

# Example
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
data = serialize(root)
print(data)   # "1,2,#,#,3,4,#,#,5,#,#"
restored = deserialize(data)
print(serialize(restored) == data)  # True

Complexity: Time O(n), Space O(n)

Problem 12: Kth Smallest Element in BST

Asked at: Amazon, Google, Microsoft

def kth_smallest(root, k):
    """
    Inorder traversal of BST = sorted sequence. Stop at kth element.
    Time: O(H + k)  Space: O(H)
    """
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val

        current = current.right

Complexity: Time O(H + k), Space O(H)

Problem 13: Construct Binary Tree from Preorder and Inorder

Asked at: Amazon, Google, Microsoft

def build_tree(preorder, inorder):
    """
    Preorder[0] = root. Find root in inorder to split left/right subtrees.
    Time: O(n^2) naive, O(n) with hash map
    Space: O(n)
    """
    if not preorder or not inorder:
        return None

    root_val = preorder[0]
    root = TreeNode(root_val)

    mid = inorder.index(root_val)  # O(n); use dict for O(1)

    root.left = build_tree(preorder[1:mid+1], inorder[:mid])
    root.right = build_tree(preorder[mid+1:], inorder[mid+1:])

    return root

Complexity: Time O(n^2) naive, O(n) with index map, Space O(n)

Problem 14: Flatten Binary Tree to Linked List

Asked at: Amazon, Microsoft

def flatten(root):
    """
    Preorder traversal, but in-place.
    Morris-like: attach left subtree between node and right subtree.
    Time: O(n)  Space: O(1)
    """
    curr = root

    while curr:
        if curr.left:
            # Find rightmost node of left subtree
            rightmost = curr.left
            while rightmost.right:
                rightmost = rightmost.right

            # Attach original right to rightmost.right
            rightmost.right = curr.right

            # Move left to right, clear left
            curr.right = curr.left
            curr.left = None

        curr = curr.right

Complexity: Time O(n), Space O(1)

Traversal vs Problem Type

Complexity Summary

Common Mistakes

1. Not handling null root: Always guard if not root: return ... at the top.
2. Confusing height with depth: Height is measured from a node to its farthest leaf (upward). Depth is from root to a node (downward).
3. Using level-order when DFS is simpler: Level-order BFS requires a queue and explicit level tracking. For problems that do not need level information, DFS is simpler.
4. Forgetting to update max in diameter: The diameter is a global maximum, not the return value of the recursive function. Use a nonlocal variable or a list.

Related Articles

• Trees Questions Placement
• Graph Traversal Patterns 2026
• Dynamic Programming Patterns 2026
• Binary Search Patterns 2026
• Must-Do Coding Questions