DFS
dfs
Algorithms
BFS & DFS (Intro)
Swap a queue for a stack inside a graph traversal and you flip from breadth-first to depth-first behavior. The visited-vertex tracking is identical, the neighbor expansion is identical, and yet one explores level by level while the other dives down the longest path first. That single data-structure swap is the entire difference between the two most-used graph algorithms in the field. **BFS & DFS (Intro)** walks through both. For BFS you will implement queue-based level-by-level exploration and use it to find shortest paths in unweighted graphs. For DFS you will see both the recursive form (which uses the call stack implicitly) and the iterative form with an explicit stack, and apply them to connectivity checks, path finding, and cycle detection. The lesson also covers the visited set that prevents infinite loops on cyclic graphs and contrasts graph traversal with tree traversal as a special case. This lesson assumes you are comfortable with three structures from the data-structures track: **Stack (LIFO)** powers iterative DFS, **Queue & Deque** powers BFS, and **Graphs: Representation Basics** gives you the adjacency list or matrix that both algorithms read from. Next, **Hashing Techniques** turns to a different building block, the hash map, which underpins many of the lookup-heavy patterns you will combine with traversal in later lessons.
Not Started
0%
Practice Problems
Balanced Binary Tree
Given the root of a binary tree, determine if it is height-balanced (the depth of the two subtrees of every node never differs by more than one).
Count Complete Tree Nodes
Given the root of a complete binary tree, return the number of nodes in the tree.
Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter (the longest path between any two nodes, measured in edges).
Flood Fill
Given a 2D grid representing an image, a starting pixel, and a new color, perform a flood fill (like a paint bucket tool) to recolor the connected region.
Invert Binary Tree
Given the root of a binary tree, invert the tree (mirror it) and return its root.
Lowest Common Ancestor of a BST
Given a binary search tree and two nodes, find their lowest common ancestor by leveraging the BST property.
Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth (the number of nodes along the longest path from root to leaf).
Path Sum
Given the root of a binary tree and a target sum, determine if the tree has a root-to-leaf path that sums to the target.
Same Tree
Given the roots of two binary trees, determine if they are the same (structurally identical with the same node values).
Subtree of Another Tree
Given the roots of two binary trees, determine if the second tree is a subtree of the first tree.
Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (symmetric around its center).
Alien Dictionary
Given a sorted list of words in an alien language, determine the order of characters in the alien alphabet using topological sort.
Binary Tree Maximum Path Sum
Given the root of a binary tree, return the maximum path sum where a path is any sequence of connected nodes (not necessarily passing through the root).
Longest Increasing Path in a Matrix
Given an m x n integer matrix, find the length of the longest strictly increasing path where you can move in four directions.
Reconstruct Itinerary
Given a list of airline tickets, reconstruct the itinerary in lexical order starting from 'JFK', using all tickets exactly once.
Serialize and Deserialize Binary Tree
Design an algorithm to serialize a binary tree to a string and deserialize the string back to the original tree.
Word Search II
Given a 2D board of characters and a list of words, find all words that can be formed by sequentially adjacent cells on the board, using each cell at most once per word.
Accounts Merge
Given a list of accounts where each account has a name and emails, merge accounts that share a common email address.
Design Add and Search Words
Design a data structure that supports adding words and searching for words with wildcard characters, where '.' can match any single letter.
Binary Tree Right Side View
Given the root of a binary tree, return the values of the nodes you can see when looking at the tree from the right side, ordered from top to bottom.
Clone Graph
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the entire graph.
Number of Connected Components
Given n nodes and a list of undirected edges, find the number of connected components in the graph.
Construct BT from Inorder and Postorder
Given inorder and postorder traversal arrays, construct the binary tree and return its root.
Construct BT from Preorder and Inorder
Given preorder and inorder traversal arrays, construct the binary tree and return its root.
Count Good Nodes in Binary Tree
Given a binary tree root, count the number of 'good' nodes where no node on the path from root to that node has a value greater than the node's value.
Course Schedule
Given a number of courses and their prerequisites, determine if it is possible to finish all courses (detect if the dependency graph has a cycle).
Evaluate Division
Given equations like a/b = k, answer queries asking for the result of x/y using graph traversal on a weighted directed graph.
Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a linked list in-place using the right pointers in preorder traversal order.
Graph Valid Tree
Given n nodes and a list of undirected edges, determine if these edges form a valid tree (connected and acyclic).
Kth Smallest Element in a BST
Given the root of a BST and an integer k, return the kth smallest value (1-indexed) using in-order traversal.
Lowest Common Ancestor of Binary Tree
Given a binary tree and two nodes, find their lowest common ancestor (the deepest node that is an ancestor of both).
Max Area of Island
Given a binary grid, find the maximum area of an island (connected group of 1s connected 4-directionally).
Minimum Absolute Difference in BST
Given a BST, find the minimum absolute difference between the values of any two different nodes using in-order traversal.
Number of Islands
Given a 2D grid of '1's (land) and '0's (water), count the number of distinct islands formed by connected land cells.
Number of Provinces
Given an adjacency matrix representing connections between cities, find the total number of provinces (connected components).
Pacific Atlantic Water Flow
Given a matrix of heights, find all cells from which water can flow to both the Pacific and Atlantic oceans.
Path Sum II
Given the root of a binary tree and a target sum, return all root-to-leaf paths where the sum of the values equals the target.
Sum Root to Leaf Numbers
Given a binary tree where each node contains a digit 0-9, find the total sum of all root-to-leaf numbers.
Surrounded Regions
Given a board of 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' (not touching the border).
Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree using bounds checking or in-order traversal.
Word Search
Given an m x n grid of characters and a string word, determine if the word exists in the grid by following a path of adjacent cells (horizontally or vertically) without reusing any cell.
Code Snippets
DFS Traversal Template
Depth-first search visits a node, then recursively visits each unvisited neighbor before backtracking. It is the natural traversal for tree problems, cycle detection, topological order, and connected-components. This snippet covers the recursive form, an iterative stack-based form for very deep graphs, and a path-tracking variant that surfaces the actual route from start to a target.
Python DFS Templates (Recursive + Iterative)
DFS visits a graph by going as deep as possible before backtracking. Python lets you write it recursively (concise, but bounded by `sys.getrecursionlimit()`) or iteratively with an explicit stack (uglier, but safe for deep graphs). This entry ships both templates and a third variant that detects cycles in a directed graph using gray / black coloring.
Question Banks
Community
House Robber III
Maximize money robbed from a binary-tree neighborhood where no two directly-connected houses can both be robbed.
Graph Algorithms 101
Why most production graph work is modeling, not algorithm; the two traversals you actually use; and the representation table that drives every memory tradeoff.
Backtracking: The Template That Solves 30 Problems
One choose, explore, unchoose template. Walk it on N-queens, then map the variations: permutations, subsets, word-search, sudoku. The pattern stays put; the predicate moves.
Recover Binary Search Tree
Two BST nodes have been swapped by mistake. Restore the BST in-place by finding and swapping them back.
Cousins in Binary Tree
Decide whether two values in a binary tree are cousins (same depth, different parents).
Two Sum IV - Input is a BST
Decide whether two distinct BST nodes sum to a target, ideally in O(n) time and O(h) extra space.
Is Graph Bipartite?
Decide whether an undirected graph admits a 2-coloring with no edge sharing a color, using BFS over each component.
Range Sum of BST
Sum every BST value within an inclusive range, pruning subtrees that fall outside.
Binary Tree Paths
Return every root-to-leaf path in a binary tree as a list of arrow-joined strings.