Trees and Graph Traversal: The Complete LeetCode Guide

Trees and graphs appear in roughly 35% of coding interviews at top tech companies. If you're preparing for a software engineering role, ignoring these data structures is not an option — they show up in LeetCode trees graphs problems at every difficulty level.

The good news is that both trees and graphs share the same two traversal strategies: depth-first search (DFS) and breadth-first search (BFS). Once you internalize these two patterns as templates, a huge swath of interview problems becomes manageable.

This guide walks you through binary tree fundamentals, DFS and BFS patterns, graph traversal techniques, and the classic LeetCode problems that appear most often in real interviews.

A binary tree is a hierarchical data structure where each node has at most two children: a left child and a right child. The topmost node is called the root, and nodes with no children are called leaves. Depth is the distance from a node to the root; height is the distance from a node to its deepest leaf.

Binary tree interview questions almost always involve visiting every node in a specific order. There are three classic traversal orders to know, each with its own use case and natural recursive structure.

Understanding these traversal orders is the foundation for solving subtree problems, path problems, and level-order problems — three of the most common binary tree problem families on LeetCode.

Recursive DFS is the most natural way to traverse a binary tree. The call stack does the heavy lifting for you — each recursive call processes a node, then delegates to left and right subtrees. The pattern is: handle the base case (null node), do work at the current node, recurse left, recurse right.

DFS shines for path problems (find all root-to-leaf paths, max path sum), subtree problems (check if a subtree matches a pattern), and anything requiring depth-first discovery. Classic examples include Binary Tree Maximum Path Sum (#124) and Validate Binary Search Tree (#98).

The time complexity of DFS on a tree is O(n) — you visit every node exactly once. Space complexity is O(h) where h is the tree height, due to the call stack. For a balanced tree that is O(log n); for a skewed tree it degrades to O(n).

Breadth-first search (BFS) processes nodes level by level, left to right. You use an explicit queue instead of the call stack. At each step, dequeue the front node, process it, and enqueue its children. This naturally groups nodes by depth.

BFS is the go-to pattern for level-order problems, shortest path problems in unweighted graphs, and any problem where you need to reason about the distance from a starting node. Binary Tree Level Order Traversal (#102) and Minimum Depth of Binary Tree (#111) are classic BFS tree problems.

The template is straightforward: initialize a queue with the root, then loop while the queue is non-empty. For level-aware problems, snapshot the queue length at the start of each iteration — that length tells you how many nodes belong to the current level.

Graphs generalize trees: nodes (vertices) connected by edges, with no required root and potentially with cycles. Most graph problems in coding interviews represent the graph as an adjacency list — a mapping from each node to its list of neighbors.

The key difference between graph traversal and tree traversal is cycle detection. In a tree, you can never revisit a node because there are no cycles. In a graph, you must track visited nodes explicitly, or you will loop forever. A simple boolean array or hash set handles this.

Both DFS and BFS work on graphs with the same templates as trees — just add a visited check before processing each node. Graph problems on LeetCode trees graphs often involve connected components, shortest paths, or cycle detection.

Three problems capture the core patterns for BFS DFS LeetCode interview questions and are worth mastering before your interview. Each one maps cleanly to a traversal template you have already seen.

Binary Tree Level Order Traversal (#102) is the canonical BFS tree problem. You collect node values level by level using a queue and a level-size snapshot. Once you can write this from memory, a dozen variants (right side view, zigzag traversal, average of levels) follow with minor modifications.

Number of Islands (#200) is the most common graph DFS problem in coding interviews. Given a 2D grid of "1"s (land) and "0"s (water), count the number of connected land components. You treat each cell as a graph node and its four neighbors as edges, then run DFS or BFS from each unvisited land cell, marking visited cells as you go.

Course Schedule (#207) introduces directed graph cycle detection. You are given course prerequisites as a directed graph; return whether it's possible to finish all courses. This reduces to detecting a cycle in a directed graph using DFS with an in-stack tracking set, or BFS topological sort (Kahn's algorithm).

The hardest part of tree and graph traversal is not the code — it's recognizing which pattern applies. Most tree problems announce themselves: "level-order" means BFS, "path" means DFS, "BST" means inorder. Graph problems are trickier because the graph may be disguised as a grid, a word list, or a course schedule.

The best way to build pattern recognition is spaced repetition on the templates, not brute-force grinding through hundreds of problems. If you can recall the DFS tree template, the BFS level-order template, and the graph traversal template with visited tracking, you can adapt them to most interview scenarios in under 10 minutes.

YeetCode's flashcard system is built around this approach. Instead of re-reading solutions, you actively recall the template steps and pattern triggers — the same mental process you'll need in an interview. Review the Trees and Graphs category on YeetCode, and focus on pattern recognition before problem quantity.

Aim to solve at least 10-15 tree problems and 5-10 graph problems before your interview. Prioritize medium difficulty, since that is the most common level in real coding rounds. Once DFS and BFS feel automatic, tackle the harder variants like word ladder, alien dictionary, and minimum spanning tree problems.