Binary Tree Vertical Order Traversal

Medium

Binary Tree Vertical Order Traversal

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type are the node values, and can they be negative, zero, or floating-point numbers?
If the tree is empty, should I return an empty list or null?
If multiple nodes are at the same vertical level, what should be the order of their values in the output?
Is the binary tree guaranteed to be a binary search tree, or can it be any general binary tree?
What should the output be if the tree has only one node?

Brute Force Solution

Approach

Imagine each node in the tree is a building, and we want to organize them based on their street address (vertical position). The brute force way is like trying every possible street address for each building and checking if that arrangement makes sense. We explore all combinations, figuring out the street layout that matches what we see in the tree.

Here's how the algorithm would work step-by-step:

First, consider every possible horizontal position for each node in the tree. This means assigning a vertical column number to each node.
Keep track of the minimum and maximum column numbers used. This helps us define the range of our vertical order.
Then, for each column number within that range (from the minimum to the maximum), go through all the nodes in the tree.
Check if the node's assigned column number matches the current column number we're looking at.
If it matches, add the node's value to a list representing that vertical order.
Repeat this process for every column number in our range.
Finally, combine all the lists we created for each column to form the final vertical order traversal.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binary_tree_vertical_order_traversal_brute_force(root):
    if not root:
        return []

    nodes_with_column = []
    minimum_column = 0
    maximum_column = 0

    def traverse_tree(node, column):
        nonlocal minimum_column, maximum_column
        if not node:
            return

        nodes_with_column.append((node, column))
        minimum_column = min(minimum_column, column)
        maximum_column = max(maximum_column, column)
        traverse_tree(node.left, column - 1)

        traverse_tree(node.right, column + 1)

    traverse_tree(root, 0)

    vertical_order = []

    # Iterate through all possible columns
    for column_number in range(minimum_column, maximum_column + 1):
        current_column_nodes = []

        # Find all nodes that belong to the current column
        for node, node_column in nodes_with_column:
            if node_column == column_number:
                current_column_nodes.append(node.val)

        # Store current column's list of nodes into result
        if current_column_nodes:
            vertical_order.append(current_column_nodes)

    return vertical_order

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm explores all possible vertical column numbers for each of the n nodes in the binary tree. It keeps track of the minimum and maximum column numbers, which in the worst case, could range from -n/2 to n/2, resulting in n columns to iterate through. For each of these n columns, the algorithm iterates through all n nodes to check if the node's column number matches the current column. Therefore, we have a nested loop structure leading to approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm explores every node in the tree, and in the worst-case scenario, where the tree is skewed, all nodes could potentially fall into different vertical orders. This requires storing each node's value in a separate list associated with its column number. Therefore, we may need to store up to N node values in separate lists, where N is the number of nodes in the tree. The min and max column numbers also contribute a constant amount of space, which is insignificant compared to the storage of node values. This results in an auxiliary space complexity of O(N).

Optimal Solution

Approach

To display a binary tree vertically, imagine each node having a horizontal position. The optimal strategy involves traversing the tree while keeping track of each node's horizontal offset, then grouping nodes by their offset to produce the vertical order.

Here's how the algorithm would work step-by-step:

Imagine each node in the tree has a 'horizontal position' relative to the root. The root is at position 0.
When moving to the left child of a node, decrease the horizontal position by 1. When moving to the right child, increase it by 1.
Traverse the entire tree (using a technique like breadth-first search) and store each node along with its horizontal position.
After visiting all nodes, group the nodes based on their horizontal positions. This means all nodes with the same horizontal position are in the same vertical line.
Sort the horizontal positions from left to right (smallest to largest).
Finally, for each horizontal position (in sorted order), list the nodes that have that position. This creates the vertical order traversal.

Code Implementation

from collections import deque

def vertical_order_traversal(root):
    if not root:
        return []

    node_horizontal_positions = {}
    queue = deque([(root, 0)])

    while queue:
        node, horizontal_position = queue.popleft()

        # Store nodes based on their horizontal position.
        if horizontal_position not in node_horizontal_positions:
            node_horizontal_positions[horizontal_position] = []

        node_horizontal_positions[horizontal_position].append(node.val)

        if node.left:
            queue.append((node.left, horizontal_position - 1))

        if node.right:
            queue.append((node.right, horizontal_position + 1))

    # Sort the horizontal positions to traverse from left to right.
    sorted_horizontal_positions = sorted(node_horizontal_positions.keys())

    # Build the final vertical order traversal list.
    vertical_order = []
    for horizontal_position in sorted_horizontal_positions:
        vertical_order.append(node_horizontal_positions[horizontal_position])

    return vertical_order

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The breadth-first search traversal visits each of the n nodes in the tree once, taking O(n) time. We store each node and its horizontal position. Grouping nodes by horizontal position involves iterating through all nodes (O(n)) and potentially inserting them into a hashmap or dictionary which takes O(1) on average. Sorting the horizontal positions is the dominant factor, typically taking O(k log k) time where k is the number of unique horizontal positions. In the worst case, k can be proportional to n, so the sorting becomes O(n log n). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The primary space complexity arises from storing the nodes and their horizontal positions during the breadth-first search. In the worst-case scenario, such as a skewed tree, we might need to store all N nodes in a queue for processing. Furthermore, we store the nodes in a hash map (or similar data structure) to group them by their horizontal positions, potentially holding all N nodes. Therefore, the auxiliary space required grows linearly with the number of nodes, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty tree	Return an empty list as there are no nodes to traverse.
Tree with only a root node	Return a list containing a single sublist with the root's value.
Skewed tree (left or right only)	The algorithm should correctly handle skewed trees by assigning appropriate column indices and traversing all nodes.
Tree with duplicate values	The algorithm should handle duplicate values correctly by including them in their respective vertical orders.
Large tree depth which can cause call stack overflow if using recursive approach	Use an iterative approach like level order traversal to avoid stack overflow for very deep trees.
Integer overflow when calculating column indices (extreme left or right)	Use a wider data type (e.g., long) for column indices or re-center the indexing to avoid overflows.
Tree with negative node values	The algorithm should correctly handle negative node values without any modification.
Tree is perfectly balanced	Algorithm should handle balanced trees efficiently and correctly place each node in the appropriate vertical order.