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.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

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.

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}

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

Solution Implementation

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

Learn more about how to find time and space complexity quickly using problem constraints.