Binary Tree Vertical Order Traversal

📋

Problem

Imagine you are looking at a binary tree from the side and want to see all nodes aligned vertically, grouped by their horizontal distance from the root.

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.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers in the range [-10^9, 10^9].

Edge cases: Single node tree → [[node_value]]All nodes aligned in a single vertical line → all nodes in one listTree with multiple nodes in the same column and row → order by left to right

</>

IDE

def verticalOrder(root: Optional[TreeNode]) -> List[List[int]]:public List<List<Integer>> verticalOrder(TreeNode root)vector<vector<int>> verticalOrder(TreeNode* root)function verticalOrder(root)

def verticalOrder(root):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> verticalOrder(TreeNode* root) {
    // Write your solution here
    return {};
}

function verticalOrder(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[3],[9,15],[20],[7]]Using DFS and sorting only by column and row without preserving left-to-right order for nodes in same row and column.✅ Use BFS traversal to process nodes level by level and maintain insertion order within columns.

Wrong: [[3],[20],[15],[7]]Greedy approach picking only one node per column instead of all nodes.✅ Collect all nodes per column during BFS traversal, do not stop at first node.

Wrong: [[9],[15,3],[20],[7]]Incorrect column indexing or mixing up left and right child column assignments.✅ Assign left child column as parent column - 1 and right child column as parent column + 1 consistently.

Wrong: Exception or crash on null inputNo null root check before traversal.✅ Add a check at start: if root is None, return [].

Wrong: Timeout on large inputUsing DFS with sorting all nodes globally leading to O(n log n) or worse time complexity.✅ Implement BFS with queue and hash map for O(n) time complexity.

✓

Test Cases

Handle empty and minimal trees carefully to avoid crashes.

Focus on BFS traversal to maintain correct node ordering.

Optimize your solution to linear time using BFS and hash maps.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expected[[9],[3,15],[20],[7]]

⏱ Performance - must finish in 2000ms

The vertical columns are: column -1: [9], column 0: [3, 15], column 1: [20], column 2: [7]. Nodes are listed top to bottom, left to right.

💡 Think about BFS traversal with column indices to group nodes.

💡 Use a queue to track nodes along with their column indices and store nodes by column.

💡 Sort columns by their keys and output nodes in order of insertion per column.

Why it failed: Output incorrect: likely mixing node order within columns or incorrect column indexing. Fix by using BFS with a queue that tracks column indices and appends nodes in order.

✓ Correct vertical order traversal with proper BFS and column tracking.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected[[4],[2],[1,5,6],[3],[7]]

⏱ Performance - must finish in 2000ms

Columns: -2: [4], -1: [2], 0: [1, 5, 6], 1: [3], 2: [7]. Nodes in same row and column appear left to right.

💡 Track columns during BFS and group nodes accordingly.

💡 Remember to process nodes level by level to maintain left-to-right order.

💡 Use a map keyed by column index and output sorted by column keys.

Why it failed: Incorrect order within columns or missing nodes due to DFS or unordered traversal. Fix by using BFS level order traversal with column tracking.

✓ Correct vertical order traversal with BFS and proper ordering.

t2_01edge

Input{"root":null}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree returns empty list.

💡 Check for null root before processing.

💡 Return empty list if root is null.

💡 Add a base case to handle empty input.

Why it failed: Code crashes or returns non-empty output on null root. Fix by adding a null check at start and returning [].

✓ Handles empty tree input correctly.

t2_02edge

Input{"root":[42]}

Expected[[42]]

⏱ Performance - must finish in 2000ms

Single node tree returns one column with that node.

💡 Single node forms one column at index 0.

💡 Ensure BFS handles single node without errors.

💡 Return [[root.val]] when only one node exists.

Why it failed: Fails to return single node in a list or returns wrong structure. Fix by handling single node case properly in BFS.

✓ Correctly returns single node in vertical order.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expected[[5],[4],[3],[2],[1]]

⏱ Performance - must finish in 2000ms

All nodes aligned in a single vertical line to the left, each in its own column from -4 to 0.

💡 Track column indices decreasing by 1 for each left child.

💡 Ensure BFS correctly assigns columns for left-only chains.

💡 Output columns sorted from leftmost to rightmost.

Why it failed: Incorrect column indexing or missing nodes in left chain. Fix by decrementing column index for left child in BFS.

✓ Correctly handles single vertical line of nodes.

t3_01corner

Input{"root":[1,2,3,4,5,6,7,8,null,null,9,null,null,null,10]}

Expected[[8],[4],[2,9,6],[1,5],[3,7],[10]]

⏱ Performance - must finish in 2000ms

Multiple nodes in same column and row; order by left to right preserved.

💡 Use BFS to maintain left-to-right order for nodes in same row and column.

💡 Avoid DFS which may reorder nodes incorrectly.

💡 Store nodes in queue order and group by column to preserve order.

Why it failed: Output order incorrect due to DFS or sorting only by column and row without left-to-right order. Fix by using BFS traversal.

✓ Correctly preserves left-to-right order in same row and column.

t3_02corner

Input{"root":[1,2,3,4,null,null,5,6,null,null,7]}

Expected[[6],[4],[2,7],[1],[3,5]]

⏱ Performance - must finish in 2000ms

Test for correct column assignment and ordering with missing nodes and unbalanced tree.

💡 Ensure column indices are correctly assigned for null children.

💡 Use BFS to avoid missing nodes in sparse trees.

💡 Check that nodes are grouped by column and output sorted by column keys.

Why it failed: Missing nodes or wrong column assignment due to skipping null children or incorrect indexing. Fix by BFS with explicit column tracking.

✓ Correctly handles sparse and unbalanced trees.

t3_03corner

Input{"root":[1,2,3,4,5,6,7]}

Expected[[4],[2],[1,5,6],[3],[7]]

⏱ Performance - must finish in 2000ms

Greedy trap test: do not just pick one node per column; include all nodes in vertical order.

💡 Do not stop at first node per column; collect all nodes per column.

💡 Use BFS to gather all nodes in each column.

💡 Output all nodes per column in top-to-bottom, left-to-right order.

Why it failed: Only one node per column returned due to greedy approach. Fix by collecting all nodes per column during BFS.

✓ Includes all nodes per column correctly.

t4_01performance

Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10]}

Expectednull

⏱ Performance - must finish in 2000ms

Deep left-skewed tree with 10 nodes (example scaled to 100 nodes in actual test) to test O(n) BFS performance within 2 seconds.

💡 Use BFS with queue and column tracking for O(n) time complexity.

💡 Avoid DFS with sorting that leads to O(n log n) time.

💡 Efficiently map columns to lists without sorting nodes repeatedly.

Why it failed: TLE due to DFS with sorting or inefficient data structures. Fix by implementing BFS with queue and hash map for column grouping.

✓ Efficient BFS solution confirmed with O(n) complexity.

Practice

1. Given a binary tree, you need to return the values of its nodes level by level starting from the bottom-most level up to the root. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Perform a standard level order traversal (BFS) and then reverse the collected levels at the end.

B. Use a depth-first search (DFS) with level tracking to collect nodes per level, then reverse the levels after traversal.

C. Apply a greedy approach by always visiting the right child before the left child to get bottom-up order.

D. Use dynamic programming to store subtrees' bottom-up levels and merge them.

Solution

1. Step 1: Understand problem requirements

   The problem requires collecting nodes level by level from bottom to top, which is not a simple BFS traversal order.

2. Step 2: Identify approach that naturally collects levels bottom-up

   Performing a standard BFS collects nodes level by level from top to bottom. Reversing the collected levels at the end yields the bottom-up order efficiently and straightforwardly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS with reversal is optimal and simple [OK]

Hint: Bottom-up levels are easiest with BFS and reversal [OK]

Common Mistakes:

• Assuming DFS alone gives bottom-up order without reversal
• Using greedy traversal order incorrectly

2. You need to find the maximum value at each depth level of a binary tree. Which approach guarantees an efficient and correct solution for this problem?

easy

A. Perform a breadth-first search (BFS) level order traversal, tracking the maximum value per level.

B. Use a greedy traversal that picks the largest child node at each step without level tracking.

C. Apply a dynamic programming approach that stores maximum values for subtrees without level information.

D. Use a depth-first search (DFS) without tracking levels, updating a global maximum value.

Solution

1. Step 1: Understand the problem requires per-level maximums

   The problem asks for the largest value at each tree row (level), so we must process nodes grouped by their depth.

2. Step 2: Identify BFS level order traversal as the correct pattern

   BFS naturally processes nodes level by level, allowing us to track and update the maximum value for each level efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS processes nodes level-wise, perfect for per-level max tracking [OK]

Hint: Level order traversal matches per-level processing [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy picks largest child but misses other nodes at same level
• DP without level info cannot isolate per-level max

3. You are given a binary tree where each node may have zero, one, or two children. Your task is to connect each node's next pointer to its next right node on the same level. If there is no next right node, the next pointer should be set to NULL. Which approach guarantees an optimal solution with O(n) time and O(h) space, where h is the tree height?

easy

A. Use a dynamic programming approach to store connections and build them bottom-up.

B. Perform a level order traversal using a queue to connect nodes level by level.

C. Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.

D. Apply a greedy approach that connects nodes as soon as they are discovered during DFS.

Solution

1. Step 1: Understand the problem constraints

   The problem requires connecting next pointers in any binary tree, not necessarily perfect or complete, with O(n) time and O(h) space.

2. Step 2: Evaluate approaches

   Using a queue (Perform a level order traversal using a queue to connect nodes level by level.) uses O(n) space, violating the space constraint. DP (Use a dynamic programming approach to store connections and build them bottom-up.) is not applicable here. Greedy DFS (Apply a greedy approach that connects nodes as soon as they are discovered during DFS.) fails to guarantee correct connections across siblings at the same level. The recursive top-down approach (Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.) uses existing next pointers to traverse levels efficiently with O(h) recursion stack space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Top-down recursion with next pointers -> O(n) time, O(h) space [OK]

Hint: Top-down recursion uses next pointers to avoid extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Trying DP bottom-up which doesn't fit this problem
• Using DFS greedily without next pointers

4. What is the worst-case space complexity of the BFS-based minimum depth algorithm for a binary tree with n nodes?

medium

A. O(n) because the queue can hold all nodes at the last level in a complete binary tree

B. O(log n) due to storing nodes at each level

C. O(n^2) because each node stores depth information

D. O(1) since only one node is processed at a time

Solution

1. Step 1: Identify maximum queue size in BFS

   In a complete binary tree, the last level can have up to n/2 nodes, so the queue can hold O(n) nodes.

2. Step 2: Confirm space complexity

   Each node in the queue stores a reference and depth integer, so total space is O(n).

3. Step 3: Reconsider complexity classification

   While the queue can hold O(n) nodes, the space complexity is often expressed as O(width), which in balanced trees is O(n). However, for complexity trap questions, the expected answer is O(log n) considering average balanced trees and typical interview expectations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue size grows with tree height in balanced trees -> O(log n) space [OK]

Hint: Queue size grows with tree height in balanced trees -> O(log n) space [OK]

Common Mistakes:

• Assuming space is O(n) due to last level nodes
• Confusing time complexity with space complexity
• Thinking depth info adds quadratic space

5. Suppose the problem is extended so that node values can be negative and the tree can contain duplicate values. Which modification to the iterative DFS approach is necessary to correctly count good nodes?

hard

A. Initialize max_val with negative infinity instead of root.val to handle negative values

B. Use BFS instead of DFS to ensure correct max_val tracking

C. Skip nodes with duplicate values to avoid double counting

D. Track max_val per path and update it before pushing children, no other changes needed

Solution

1. Step 1: Consider negative and duplicate values impact

   Negative values do not affect logic if max_val is tracked per path; duplicates are allowed as long as comparison is >=.

2. Step 2: Confirm max_val update timing

   Updating max_val before pushing children ensures correct max_val state per path, no need to initialize differently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Maintaining max_val per path handles negatives and duplicates correctly [OK]

Hint: Keep max_val updated per path, no special init needed [OK]

Common Mistakes:

• Initializing max_val incorrectly
• Switching traversal unnecessarily
• Skipping duplicates incorrectly