III. Tree Traversal Patterns (DFS & BFS)

Pattern 1: Level Order Traversal (BFS)

This is the standard Breadth-First Search (BFS) for trees. Instead of going deep, you explore the tree level by level.

The Logic: Use a Queue to track nodes.

1. Initialize the queue with the root.

2. While the queue is not empty, determine the current level_size Iterate level_size times to process all nodes at the current depth.

3. For each node, add its left and right children to the queue for the next level.

   Time Complexity: O(N) — every node is visited once.

   Example Problems: 102. Binary Tree Level Order Traversal, 103. Binary Tree Zigzag Level Order Traversal, 199. Binary Tree Right Side View, 515. Find Largest Value in Each Tree Row, 1161. Maximum Level Sum of a Binary Tree.

Pattern 2: Recursive Preorder Traversal (DFS)

A Depth-First Search (DFS) pattern where the current node is processed before its children. The Logic: Process the root, then recurse on the left child, then recurse on the right child (Root → Left → Right). This is ideal for problems where you need to pass information from the parent down to the children (e.g., building a path or cloning a tree).

Time Complexity: O(N).

Example Problems: 100. Same Tree, 101. Symmetric Tree, 105. Construct Binary Tree from Preorder and Inorder Traversal, 114. Flatten Binary Tree to Linked List, 226. Invert Binary Tree, 257. Binary Tree Paths, 988. Smallest String Starting From Leaf.

Pattern 3: Recursive Inorder Traversal (DFS)

Pattern 14: Recursive Inorder Traversal (DFS)

A DFS pattern where the current node is processed between its children.

The Logic: Recurse on the left child, process the root, then recurse on the right child (Left → Root → Right).

The BST Connection: In a Binary Search Tree (BST), an inorder traversal visits nodes in sorted ascending order. If you see a BST problem involving sorting, validation, or finding the Kth element, this is almost always the answer.

Time Complexity: O(N).

Example Problems: 94. Binary Tree Inorder Traversal, 98. Validate Binary Search Tree, 173. Binary Search Tree Iterator, 230. Kth Smallest Element in a BST, 501. Find Mode in Binary Search Tree, 530. Minimum Absolute Difference in BST.

Pattern 4: Recursive Postorder Traversal (DFS)

A DFS pattern where the current node is processed after its children.

The Logic: Recurse left, recurse right, then process the root (Left → Right → Root). This is a "bottom-up" approach.

The "Information Gathering" Pattern: Use this when you need to collect data from subtrees (like height, sum, or balance status) before making a decision at the parent node.

Time Complexity: $O(N)$.

Example Problems: 104. Maximum Depth of Binary Tree, 110. Balanced Binary Tree, 124. Binary Tree Maximum Path Sum, 145. Binary Tree Postorder Traversal, 337. House Robber III, 366. Find Leaves of Binary Tree, 543. Diameter of Binary Tree, 863. All Nodes Distance K in Binary Tree, 1110. Delete Nodes And Return Forest.

Pattern 5: Lowest Common Ancestor

A specific application of DFS used to find the deepest node that is an ancestor to two given nodes.

The Logic:

1. If the current root is null or matches either target node, return the root.

2. Recursively search the left and right subtrees.

3. If both recursive calls return a non-null value, the current root is the LCA.

4. If only one call returns a value, return that value (propagate the found node up).

Time Complexity: $O(N)$.

Example Problems: 235. Lowest Common Ancestor of a Binary Search Tree, 236. Lowest Common Ancestor of a Binary Tree.

Pattern 6: Serialization and Deserialization

The process of converting a tree structure into a flat string/array (serialization) and back into a tree (deserialization).

The Logic: - To Serialize: Use any DFS or BFS traversal. The key is to record null pointers explicitly (e.g., as "#" or "None") so the unique structure can be rebuilt.

• To Deserialize: Use a pointer or a queue to consume the flattened data, rebuilding the tree recursively using the same traversal order used during serialization.

  Time Complexity: $O(N)$.

  Example Problems: 297. Serialize and Deserialize Binary Tree, 572. Subtree of Another Tree, 652. Find Duplicate Subtrees.