Binary Tree Vertical Order Traversal - Video Solutions
BINARY TREE VERTICAL ORDER TRAVERSAL | PYTHON SOLUTION EXPLAINED | LEETCODE 314
Binary Tree Vertical Order Traversal - Video Solution
Watch 10 video solutions for Binary Tree Vertical Order Traversal, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by Cracking FAANG has 18,018 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]
Example 2:
Input: root = [3,9,8,4,0,1,7] Output: [[4],[9],[3,0,1],[8],[7]]
Example 3:
Input: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6] Output: [[4],[2,5],[1,10,9,6],[3],[11]]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach Overview
Problem Overview: Given the root of a binary tree, return the vertical order traversal of its nodes. Nodes that lie in the same vertical column must be grouped together from top to bottom, and columns are processed from leftmost to rightmost.
Approach 1: DFS with Column Tracking + Sorting (O(n log n) time, O(n) space)
This method performs a depth-first search while tracking each node’s column index. The root starts at column 0, the left child moves to col - 1, and the right child moves to col + 1. Store nodes in a hash table where the key is the column index and the value is a list of nodes discovered in that column. DFS visits nodes in preorder, so the insertion order alone does not guarantee top-to-bottom ordering across branches. To produce the final vertical order, collect the columns and sort them from smallest to largest before building the output. This approach is straightforward to implement and works well when you already have a DFS traversal structure in place.
Approach 2: BFS with Column Tracking (O(n) time, O(n) space)
The optimal solution uses breadth-first search. BFS naturally processes nodes level by level, which preserves the required top-to-bottom ordering within each vertical column. Maintain a queue storing pairs of (node, column). For every node popped from the queue, append its value to the list mapped to its column in a hash map. Push the left child with col - 1 and the right child with col + 1. Track the minimum and maximum column indices during traversal so you can iterate from the leftmost column to the rightmost without sorting. Each node is processed exactly once, making the traversal linear.
Recommended for interviews: The BFS approach is what most interviewers expect. It preserves vertical ordering naturally and avoids an extra sorting step, resulting in O(n) time complexity. Demonstrating the DFS approach first shows you understand how column indexing works in a binary tree, but switching to BFS shows stronger algorithmic judgment and awareness of traversal properties.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Hash Map + Column Sorting | O(n log n) | O(n) | When using recursive traversal or when node ordering is not strictly tied to level order |
| BFS with Column Tracking | O(n) | O(n) | General case and preferred interview solution since BFS preserves vertical ordering |