LeetCode Patterns Flashcards: Trees, DFS, BFS, Traversals, BST Properties

Depth-first search, or DFS, explores as deep as possible along each branch before backtracking. It uses recursion or an explicit stack and processes nodes in preorder, inorder, or postorder sequences. DFS uses O of h space where h is the tree height. Breadth-first search, or BFS, explores all nodes at the current level before moving to the next level. It uses a queue and processes nodes level by level. BFS uses O of w space where w is the maximum width. Use DFS when the answer involves paths from root to leaf or when you need to explore all possibilities.

All three are depth-first traversal orders differing in when the current node is processed relative to its children. Preorder processes the node first, then left subtree, then right subtree. It is useful for copying or serializing a tree. Inorder processes left subtree, then the node, then right subtree. On a binary search tree, inorder produces elements in sorted ascending order. Postorder processes left subtree, then right subtree, then the node last. It is useful for deleting a tree or calculating sizes because children are processed before parents.

Initialize a queue with the root node. While the queue is not empty, record the queue size as the number of nodes at the current level. Process exactly that many nodes by dequeuing each one, recording its value, and enqueuing its left and right children if they exist. After processing all nodes at one level, the queue contains exactly the nodes of the next level. This naturally groups nodes by level and runs in O of n time and O of w space. Level-order traversal is the foundation for problems like finding the maximum value at each level, the right-side view of a tree, and the zigzag traversal.

A binary search tree, or BST, maintains the invariant that every node in the left subtree has a value less than the current node, and every node in the right subtree has a value greater. This enables O of log n search, insertion, and deletion in balanced trees. To validate a BST, perform an inorder traversal and verify the values are in strictly ascending order, or recursively pass down valid ranges for each node. A common mistake is checking only the immediate children instead of the entire subtree.

The lowest common ancestor, or LCA, is the deepest node that has both target nodes as descendants, where a node can be its own ancestor. Use DFS: if the current node is null or equals either target, return the current node. Recursively search left and right subtrees. If both recursive calls return non-null, the current node is the LCA because one target is in each subtree. If only one returns non-null, propagate that result upward. For a BST, the solution is simpler: if both targets are smaller, go left; if both are larger, go right; otherwise the current node is the LCA.

Use DFS recursion: the maximum depth of a node is one plus the maximum of the depths of its left and right children. The base case is a null node with depth zero. This naturally computes the answer bottom-up in O of n time and O of h space on the call stack. Alternatively, use BFS and count the number of levels processed, which also gives the maximum depth in O of n time. Maximum depth is equivalent to height for the root node. This simple recursive pattern is the foundation for more complex tree problems like diameter, balanced tree check, and subtree problems.

Serialization converts a tree into a string representation, and deserialization reconstructs the tree from the string. Use preorder DFS: record each node's value, and use a special marker like "null" for null children. The string becomes a comma-separated sequence of values and null markers. To deserialize, iterate through the values: each value creates a node, recursively build its left then right children, and null markers return null to stop recursion. The preorder traversal with null markers captures the complete tree structure because the null markers encode where subtrees end. ---