Skip to main content
Talentd

Binary Tree Vertical Order Traversal - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableTreeDepth-First SearchBreadth-First Search10 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

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.

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS—
BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Hash Map + Column SortingO(n log n)O(n)When using recursive traversal or when node ordering is not strictly tied to level order
BFS with Column TrackingO(n)O(n)General case and preferred interview solution since BFS preserves vertical ordering

Video Solution

BINARY TREE VERTICAL ORDER TRAVERSAL | PYTHON SOLUTION EXPLAINED | LEETCODE 314 • Cracking FAANG • 18,018 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Binary Tree Vertical Order Traversal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Level Order Traversal