Binary Tree Vertical Order Traversal solution and explanation
Google
9 more videos on this problem
BINARY TREE VERTICAL ORDER TRAVERSAL | PYTHON SOLUTION EXPLAINED | LEETCODE 314Cracking FAANG · 13:13 · 18K views
Binary Tree Vertical Order Traversal - Leetcode 314 - PythonNeetCodeIO · 12:14 · 16K views
LeetCode 314. Binary Tree Vertical Order Traversal Explanation and Solutionhappygirlzt · 7:23 · 8K views
Leetcode 314. Binary Tree Vertical Order TraversalNeedCode⚡ · 9:22 · 4K views
Leetcode 314/987 Binary Tree Vertical Order TraversalRen Zhang · 13:12 · 2K views
Binary Tree Vertical Order Traversal - LeetCode 314 - Python #leetcode #binarytreeDeepti Talesra · 14:47 · 2K views
LeetCode 314. Binary Tree Vertical Order TraversalKacy Codes · 12:37 · 1K views
Binary Tree Vertical Order Traversal - LeetCode 314 - JavaScriptAlgoJS · 6:14 · 1K views
LeetCode 314. Binary Tree Vertical Order Traversal| JSer - JavaScript & AlgorithmJSer · 14:22 · 394 views
LeetCode 314: Binary Tree Vertical Order Traversal C++ In Plain English (Facebook Interview)Algo Genius · 11:49 · 229 views
The problem
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.
Approach 1: DFS
DFS traverses the binary tree, recording the value, depth, and horizontal offset of each node. Then sort all nodes by horizontal offset from small to large, then by depth from small to large, and finally group by horizontal offset.
The time complexity is O(nlog log n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(root, depth, offset):
if root is None:
return
d[offset].append((depth, root.val))
dfs(root.left, depth + 1, offset - 1)
dfs(root.right, depth + 1, offset + 1)
d = defaultdict(list)
dfs(root, 0, 0)
ans = []
for _, v in sorted(d.items()):
v.sort(key=lambda x: x[0])
ans.append([x[1] for x in v])
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeMap<Integer, List<int[]>> d = new TreeMap<>();
public List<List<Integer>> verticalOrder(TreeNode root) {
dfs(root, 0, 0);
List<List<Integer>> ans = new ArrayList<>();
for (var v : d.values()) {
Collections.sort(v, (a, b) -> a[0] - b[0]);
List<Integer> t = new ArrayList<>();
for (var e : v) {
t.add(e[1]);
}
ans.add(t);
}
return ans;
}
private void dfs(TreeNode root, int depth, int offset) {
if (root == null) {
return;
}
d.computeIfAbsent(offset, k -> new ArrayList<>()).add(new int[] {depth, root.val});
dfs(root.left, depth + 1, offset - 1);
dfs(root.right, depth + 1, offset + 1);
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
using pii = pair<int, int>;
class Solution {
public:
map<int, vector<pii>> d;
vector<vector<int>> verticalOrder(TreeNode* root) {
dfs(root, 0, 0);
vector<vector<int>> ans;
for (auto& [_, v] : d) {
sort(v.begin(), v.end(), [&](pii& a, pii& b) {
return a.first < b.first;
});
vector<int> t;
for (auto& x : v) {
t.push_back(x.second);
}
ans.push_back(t);
}
return ans;
}
void dfs(TreeNode* root, int depth, int offset) {
if (!root) return;
d[offset].push_back({depth, root->val});
dfs(root->left, depth + 1, offset - 1);
dfs(root->right, depth + 1, offset + 1);
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func verticalOrder(root *TreeNode) [][]int {
d := map[int][][]int{}
var dfs func(*TreeNode, int, int)
dfs = func(root *TreeNode, depth, offset int) {
if root == nil {
return
}
d[offset] = append(d[offset], []int{depth, root.Val})
dfs(root.Left, depth+1, offset-1)
dfs(root.Right, depth+1, offset+1)
}
dfs(root, 0, 0)
idx := []int{}
for i := range d {
idx = append(idx, i)
}
sort.Ints(idx)
ans := [][]int{}
for _, i := range idx {
v := d[i]
sort.SliceStable(v, func(i, j int) bool { return v[i][0] < v[j][0] })
t := []int{}
for _, x := range v {
t = append(t, x[1])
}
ans = append(ans, t)
}
return ans
}Approach 2: BFS
A better approach to this problem should be BFS, traversing from top to bottom level by level.
The time complexity is O(nlog n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
q = deque([(root, 0)])
d = defaultdict(list)
while q:
for _ in range(len(q)):
root, offset = q.popleft()
d[offset].append(root.val)
if root.left:
q.append((root.left, offset - 1))
if root.right:
q.append((root.right, offset + 1))
return [v for _, v in sorted(d.items())]/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<Pair<TreeNode, Integer>> q = new ArrayDeque<>();
q.offer(new Pair<>(root, 0));
TreeMap<Integer, List<Integer>> d = new TreeMap<>();
while (!q.isEmpty()) {
for (int n = q.size(); n > 0; --n) {
var p = q.pollFirst();
root = p.getKey();
int offset = p.getValue();
d.computeIfAbsent(offset, k -> new ArrayList()).add(root.val);
if (root.left != null) {
q.offer(new Pair<>(root.left, offset - 1));
}
if (root.right != null) {
q.offer(new Pair<>(root.right, offset + 1));
}
}
}
return new ArrayList<>(d.values());
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
map<int, vector<int>> d;
queue<pair<TreeNode*, int>> q{{{root, 0}}};
while (!q.empty()) {
for (int n = q.size(); n; --n) {
auto p = q.front();
q.pop();
root = p.first;
int offset = p.second;
d[offset].push_back(root->val);
if (root->left) q.push({root->left, offset - 1});
if (root->right) q.push({root->right, offset + 1});
}
}
for (auto& [_, v] : d) {
ans.push_back(v);
}
return ans;
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func verticalOrder(root *TreeNode) [][]int {
ans := [][]int{}
if root == nil {
return ans
}
d := map[int][]int{}
q := []pair{pair{root, 0}}
for len(q) > 0 {
for n := len(q); n > 0; n-- {
p := q[0]
q = q[1:]
root = p.node
offset := p.offset
d[offset] = append(d[offset], root.Val)
if root.Left != nil {
q = append(q, pair{root.Left, offset - 1})
}
if root.Right != nil {
q = append(q, pair{root.Right, offset + 1})
}
}
}
idx := []int{}
for i := range d {
idx = append(idx, i)
}
sort.Ints(idx)
for _, i := range idx {
ans = append(ans, d[i])
}
return ans
}
type pair struct {
node *TreeNode
offset int
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS | – |
| BFS | – |
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 |
Frequently asked questions
Is Binary Tree Vertical Order Traversal easy or hard?
The problem is generally classified as medium difficulty. The challenge lies in correctly tracking column indices while maintaining the required top-to-bottom ordering. Once you recognize that BFS naturally preserves level order, the implementation becomes straightforward.
Binary Tree Vertical Order Traversal Python/Java solution
Implementations typically use BFS with a queue of (node, column) pairs. Python solutions often use collections.deque and defaultdict, while Java implementations rely on Queue and HashMap. Both versions achieve O(n) time and O(n) space complexity.
How to solve Binary Tree Vertical Order Traversal in O(n)?
Use BFS with a queue storing (node, column) pairs. Maintain a hash map from column index to a list of node values. Track the minimum and maximum column indices during traversal so the final result can be constructed without sorting. Each node is visited once, giving O(n) time complexity.
What is the best approach for Binary Tree Vertical Order Traversal?
Breadth-first search with column indexing is the most common approach. Each node is processed with its column number while a hash map groups nodes belonging to the same column. BFS guarantees nodes are visited level by level, which preserves top-to-bottom order. The solution runs in O(n) time and O(n) space.
Is Binary Tree Vertical Order Traversal asked at Google/Amazon/Meta?
Binary tree traversal variations frequently appear in interviews at companies like Google, Amazon, and Meta. Vertical order traversal specifically tests understanding of BFS, coordinate mapping, and hash map grouping. It is a common medium-level problem in technical interview prep sets.
What data structure is used in Binary Tree Vertical Order Traversal?
The core data structures are a queue for BFS traversal and a hash map that maps column indices to lists of node values. The queue ensures nodes are processed level by level, while the hash map groups nodes belonging to the same vertical column.
What is the time complexity of Binary Tree Vertical Order Traversal?
The optimal BFS solution runs in O(n) time because every node in the binary tree is visited exactly once. Space complexity is also O(n) due to the queue and the hash map storing column groups. A DFS-based solution usually requires sorting column indices, increasing time complexity to O(n log n).