314. Binary Tree Vertical Order Traversal


Problem Description

The given problem entails processing a binary tree to perform a vertical order traversal. The binary tree is a data structure where each node has at most two children referred to as the left and right child. In a vertical order traversal, we are required to group and print out the values of the nodes that are in the same vertical level—imagine drawing vertical lines through the nodes. The nodes that intersect with the same line are in the same vertical level and should be grouped together.

When we refer to "from top to bottom, column by column," we mean that the output should be arranged so that values in higher rows of the tree are presented before lower ones, and for values in the same row, they should be listed from left to right. If we visualize the tree spatially, imagine that the root node is at position 0, nodes to the left are in negative positions (-1, -2, ...), and nodes to the right are in positive positions (+1, +2, ...). The goal is to list all nodes' values at position -n, then -n+1, all the way to 0, and then +1, +2, ... +n.

Intuition

To achieve the vertical order traversal, one intuitive approach is to perform a level-order traversal (also known as a breadth-first search), while at the same time tracking the horizontal distance from the root node for each node encountered. We need to keep a data structure to maintain groups of nodes that share the same vertical level—this can be facilitated by a dictionary where the key represents the vertical level (the horizontal distance) and the value is a list containing the nodes' values at that level.

Here are the steps we might intuitively follow to come up with the solution:

  1. We start with the root node, which will be at horizontal distance 0.
  2. We use a queue to perform the level-order traversal, and as we dequeue a node, we record its value in our dictionary under its associated horizontal distance.
  3. For every node we process, we enqueue its left child (if not null) with the horizontal distance decremented by 1, and its right child (if not null) with the horizontal distance incremented by 1.
  4. After we have traversed the entire tree, we will have a dictionary filled with vertical levels as keys and lists of node values as values. The only thing left would be to sort these keys and output the associated lists in the sorted order.

Using this approach, we ensure that nodes higher up in the tree are processed before lower nodes due to the nature of level-order traversal; and within the same level, from left to right as the left child is enqueued before the right child. In the end, when sorting the keys of our dictionary, we guarantee that the output respects the "column by column" requirement.

Solution Approach

To implement the vertical order traversal, the Reference Solution Approach uses several programming concepts and data structures:

  1. Breadth-first search (BFS): This algorithm is used for traversing the binary tree level by level from the root. It utilizes a queue (in Python, a deque) to process nodes in a first-in-first-out (FIFO) manner, which aligns with the BFS traversal pattern.

  2. Queue (deque): A deque (double-ended queue) is used here as it provides an efficient way to pop elements from the front (with popleft()) while new nodes are added to the back (with append()). For each iteration, nodes at the current level are popped and their children are added to the queue for subsequent levels.

  3. Dictionary: The defaultdict is a type of dictionary that automatically creates a new entry with a default value (list in this case) if the key doesn't exist. In the given problem, the key is the horizontal offset and the value is a list that accumulates nodes' values at that offset.

  4. Sorting: Finally, the keys representing the horizontal offsets need to be sorted to ensure the "column by column" output. This is done at the end of the BFS, once all the nodes have been processed.

Now, let's break down the steps of the implementation matching with the code:

  • Initialize an empty deque named q and a defaultdict named d. We start by adding a tuple containing the root node and its horizontal offset 0 to q. (q = deque([(root, 0)]))

  • A while loop is used to iterate over q until it's empty, indicating that all nodes have been processed. On each iteration, it processes all nodes at the current level before moving to the next.

  • Within the loop, iterate over the number of elements currently in the queue, which represents the nodes at the current level. For each element:

    • Pop it from the queue (root, offset = q.popleft()).
    • Append the node's value to the list in the dictionary associated with the current horizontal offset (d[offset].append(root.val)).
  • After processing the current node, if it has a left child, append this child along with the updated offset (offset - 1) to q. Similarly, if there's a right child, append it with offset + 1.

  • After the while loop, the dictionary now contains all the values grouped by their vertical levels but not necessarily in the correct order. Using list comprehension, we create a sorted list from the dictionary items ([v for _, v in sorted(d.items())]), where _ is a placeholder for the key (offset) which we are not explicitly using in the final list.

By sorting the items of the dictionary based on the keys (which are offsets), and then selecting only the values (lists of node values), we obtain the final vertical order traversal of the binary tree.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a simple binary tree as our example to illustrate the solution approach:

1    1
2   / \
3  2   3
4 /     \
54       5

Here's how we would perform the vertical order traversal:

  1. Begin with the root node 1, which is at horizontal distance 0. Our queue q will initially have the entry [(1, 0)] and our dictionary d is empty.

  2. We process the nodes level by level. For node 1, we dequeue it, adding 1 to the list in d for key 0 (d[0] = [1]).

  3. Then, we add its children nodes 2 with horizontal distance -1 and 3 with horizontal distance +1 to the queue (q = [(2, -1), (3, +1)]).

  4. Proceeding with the BFS, we dequeue the next element from q, which is (2, -1). Node 2's value is then added to d[-1]. After this, we enqueue its child 4 with horizontal distance -2 (q = [(3, +1), (4, -2)]).

  5. Next, we dequeue (3, +1) from the queue and add 3 to d[1]. Node 3 has a right child 5, which we will enqueue with horizontal distance +2 (q = [(4, -2), (5, +2)]).

  6. Continue until the queue is empty; dequeue (4, -2) and add 4 to d[-2]. 4 has no children, so the queue now is [(5, +2)].

  7. Finally, dequeue (5, +2) and add 5 to d[2]. Now the queue is empty, and our dictionary d is filled with the sorted keys/values like so:

1{
2  -2: [4],
3  -1: [2],
4   0: [1],
5   1: [3],
6   2: [5]
7}
  1. The last step is to sort the keys of the dictionary and arrange the values. The keys when sorted give -2, -1, 0, 1, 2. Taking the associated lists, we can now create our vertically ordered list:
1[
2  [4],  // for horizontal distance -2
3  [2],  // for horizontal distance -1
4  [1],  // for horizontal distance 0
5  [3],  // for horizontal distance 1
6  [5]   // for horizontal distance 2
7]

Thus, the vertical order traversal of the tree is [[4], [2], [1], [3], [5]]. This output respects the vertical levels of the tree from left to right and top to bottom.

Python Solution

1from collections import deque, defaultdict
2from typing import List, Optional
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
13        # If the tree is empty, return an empty list.
14        if not root:
15            return []
16
17        # Initialize a double-ended queue to hold nodes along with their horizontal distances.
18        node_queue = deque([(root, 0)])
19        # Use a default dictionary to map horizontal distances to list of node values.
20        column_table = defaultdict(list)
21
22        # Perform a breadth-first search.
23        while node_queue:
24            # Process nodes level by level.
25            for _ in range(len(node_queue)):
26                current_node, horizontal_distance = node_queue.popleft()
27                # Append the node's value to the list of its respective horizontal distance.
28                column_table[horizontal_distance].append(current_node.val)
29
30                # If the left child exists, add it to the queue with the horizontal distance decremented.
31                if current_node.left:
32                    node_queue.append((current_node.left, horizontal_distance - 1))
33                # If the right child exists, add it to the queue with the horizontal distance incremented.
34                if current_node.right:
35                    node_queue.append((current_node.right, horizontal_distance + 1))
36
37        # Sort the dictionary by horizontal distance and return the vertical order traversal.
38        return [values for _, values in sorted(column_table.items())]
39

Java Solution

1import java.util.*;
2
3/**
4 * Definition for a binary tree node.
5 * public class TreeNode {
6 *     int val;
7 *     TreeNode left;
8 *     TreeNode right;
9 *     TreeNode() {}
10 *     TreeNode(int val) { this.val = val; }
11 *     TreeNode(int val, TreeNode left, TreeNode right) {
12 *         this.val = val;
13 *         this.left = left;
14 *         this.right = right;
15 *     }
16 * }
17 */
18class Solution {
19    // Definition of Pair class to hold a TreeNode and an Integer value together
20    private static class Pair {
21        TreeNode node;
22        Integer value;
23
24        public Pair(TreeNode node, Integer value) {
25            this.node = node;
26            this.value = value;
27        }
28
29        public TreeNode getKey() {
30            return node;
31        }
32
33        public Integer getValue() {
34            return value;
35        }
36    }
37  
38    public List<List<Integer>> verticalOrder(TreeNode root) {
39        // Initialize result list
40        List<List<Integer>> result = new ArrayList<>();
41        // Early return if root is null
42        if (root == null) {
43            return result;
44        }
45
46        // Create a deque to perform a level-order traversal
47        Deque<Pair> queue = new ArrayDeque<>();
48        // Offering the root node with column value 0
49        queue.offer(new Pair(root, 0));
50        // TreeMap to hold nodes values grouped by their column number
51        TreeMap<Integer, List<Integer>> columnMap = new TreeMap<>();
52      
53        // While there are nodes in the queue, process each level
54        while (!queue.isEmpty()) {
55            Pair currentPair = queue.pollFirst();
56            TreeNode currentNode = currentPair.getKey();
57            int column = currentPair.getValue();
58            // Add the current node's value to the corresponding column list
59            columnMap.computeIfAbsent(column, k -> new ArrayList<>()).add(currentNode.val);
60            // Offer the left child with column - 1 if it exists
61            if (currentNode.left != null) {
62                queue.offer(new Pair(currentNode.left, column - 1));
63            }
64            // Offer the right child with column + 1 if it exists
65            if (currentNode.right != null) {
66                queue.offer(new Pair(currentNode.right, column + 1));
67            }
68        }
69        // Add each column's list of nodes to result list and return it
70        result.addAll(columnMap.values());
71        return result;
72    }
73}
74

C++ Solution

1#include <vector>
2#include <map>
3#include <queue>
4using namespace std;
5
6// Definition for a binary tree node.
7struct TreeNode {
8    int val;
9    TreeNode *left;
10    TreeNode *right;
11    TreeNode() : val(0), left(nullptr), right(nullptr) {}
12    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18    vector<vector<int>> verticalOrder(TreeNode* root) {
19        vector<vector<int>> verticalTraversal; // Resultant list of vertical order traversal
20        if (!root) return verticalTraversal; // If the tree is empty, return an empty list
21
22        map<int, vector<int>> columnTable; // Map to hold nodes' values under the same offset (column)
23        queue<pair<TreeNode*, int>> nodesQueue; // Queue to perform BFS, holding node pointers and their offsets
24      
25        nodesQueue.push({root, 0}); // Initialize queue with the root node at offset 0
26      
27        // Perform a breadth-first traversal of the tree
28        while (!nodesQueue.empty()) {
29            int levelSize = nodesQueue.size(); // Number of elements at current level
30            for (int i = 0; i < levelSize; ++i) {
31                auto nodeInfo = nodesQueue.front(); // Get the front pair (node and its offset)
32                nodesQueue.pop();
33                TreeNode* currentNode = nodeInfo.first;
34                int column = nodeInfo.second; // Extract offset
35              
36                columnTable[column].push_back(currentNode->val); // Append current node's value to its column list
37              
38                // If left child exists, add it to queue with updated column value (column - 1)
39                if (currentNode->left) {
40                    nodesQueue.push({currentNode->left, column - 1});
41                }
42                // If right child exists, add it to queue with updated column value (column + 1)
43                if (currentNode->right) {
44                    nodesQueue.push({currentNode->right, column + 1});
45                }
46            }
47        }
48      
49        // Transfer the map values into the final vector
50        // Map is ordered by key (column offset), so traversal is vertical and from left to right
51        for (auto &columnPair : columnTable) {
52            verticalTraversal.push_back(columnPair.second);
53        }
54      
55        return verticalTraversal; // Return the organized list of values
56    }
57};
58

Typescript Solution

1// Importing the necessary libraries is not required in TypeScript as it would be in C++.
2
3// Definition for a binary tree node.
4class TreeNode {
5    val: number;
6    left: TreeNode | null;
7    right: TreeNode | null;
8
9    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
10        this.val = val;
11        this.left = left;
12        this.right = right;
13    }
14}
15
16// Typing for the column table map, where the key is number and value is array of numbers.
17type ColumnTable = Map<number, number[]>;
18
19// Stores the result of the vertical order traversal.
20let verticalTraversal: number[][] = [];
21
22// Returns a list of vertical order traversal of a binary tree.
23function verticalOrder(root: TreeNode | null): number[][] {
24    verticalTraversal = [];
25    if (!root) return verticalTraversal; // If the tree is empty, return an empty list.
26
27    const columnTable: ColumnTable = new Map<number, number[]>();
28    const nodesQueue: Array<{ node: TreeNode; column: number }> = [];
29
30    nodesQueue.push({ node: root, column: 0 }); // Initialize queue with the root node at column 0.
31
32    // Perform a breadth-first traversal of the tree.
33    while (nodesQueue.length > 0) {
34        const levelSize = nodesQueue.length; // Number of elements at the current level.
35        for (let i = 0; i < levelSize; ++i) {
36            const { node: currentNode, column } = nodesQueue.shift()!; // Get and remove the front item from the queue.
37
38            // Append current node's value to its column list.
39            if (!columnTable.has(column)) {
40                columnTable.set(column, []);
41            }
42            columnTable.get(column)!.push(currentNode.val);
43
44            // If left or right child exists, add them to queue with updated column value.
45            if (currentNode.left) {
46                nodesQueue.push({ node: currentNode.left, column: column - 1 });
47            }
48            if (currentNode.right) {
49                nodesQueue.push({ node: currentNode.right, column: column + 1 });
50            }
51        }
52    }
53
54    // Transfer the values from the column table map into the final sorted array.
55    // The map's keys are sorted, so traversal will be vertical and from left to right.
56    const sortedColumns = Array.from(columnTable.keys()).sort((a, b) => a - b);
57    for (const column of sortedColumns) {
58        verticalTraversal.push(columnTable.get(column)!);
59    }
60
61    return verticalTraversal; // Return the organized list of values.
62}
63

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the number of nodes in the binary tree and the number of operations performed for each node.

Since the code traverses each node exactly once using a breadth-first search (BFS) approach, the iteration over nodes contributes O(N) to the time complexity, where N is the number of nodes in the tree.

For each node, few constant-time operations are performed, such as appending to a list and adding nodes to the queue. Therefore, these operations don't affect the overall time complexity which remains linear with respect to the number of nodes.

In addition, after the BFS traversal is done, the dictionary d that has been constructed is sorted by keys (vertical columns indices). If there are k entries (unique vertical indices), the sorting will take O(k log k) time.

Combining the two parts, the total time complexity is O(N + k log k). However, since in the worst case, k could be as large as N (imagine a skewed tree), the time complexity can be simplified to O(N log N).

Space Complexity

The space complexity is determined by the space needed to store the output and the data structures used during the BFS traversal.

The space taken by the dictionary d is O(N), as it stores a list of nodes for each unique vertical index. In a complete binary tree, k can be O(N), hence space complexity for d can reach O(N).

The queue q used for BFS might at most contain all the nodes at the widest level of the tree. In a perfect binary tree, this could be as much as N/2 (the last level of the tree). Therefore, the space complexity for q is O(N).

Since the output list is basically the values from the dictionary sorted by keys and does not occupy additional space unrelated to input, and considering both q and d, the overall space complexity of the algorithm is O(N).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫