Depth-First Search
See all coding puzzles and patterns here.
Algorithm Description
A depth-first search is an algorithm wherein a data structure is modeled into a tree and is traversed down toward the leaves of the tree first before continuing to other branches, in search of a target element. A breadth-first search, by comparison, traverses each level of the tree before continuing to the next level. In particular, the siblings of a leaf are traversed before the cousins of a leaf.
Depth-first search should be used when trying to determine if there is any path between two nodes.
Depth-first search can be implemented iteratively using a stack. On each iteration, the top-most (most recently encountered) item is popped off the stack and processed.
The use of a stack vs. a queue is what distinguishes a DFS (stack) from a BFS (queue).
Performance Characteristics
Let $n$ equal the number of nodes in the tree.
In the worst case, the tree might be a linked list, which means the space complexity will be $O(n)$.
Since we may need to visit every node, the runtime complexity of this technique is also $O(n)$.
Puzzles
| Puzzle | Difficulty | External Link |
| All Nodes Distance K in a Binary Tree | Medium | Leetcode 863 |
| Binary Tree Max Sum | Medium | |
| Clone a Graph | Medium | Leetcode 133 |
| Convert Binary Search Tree to Sorted Doubly Linked List | Medium | Leetcode 426 (Premium) |
| Course Schedule | Medium | Leetcode 207 |
| Diameter of a Binary Tree | Easy | Leetcode 543 |
| House Robber III | Medium | Leetcode 337 |
| Letter Combinations of a Phone Number | Medium | Leetcode 17 |
| Longest Increasing Subsequence | Medium | Leetcode 300 |
| Number of Enclaves | Medium | Leetcode 1020 |
| Valid Palindrome III | Hard | Leetcode 1216 (Premium) |
