NUHMAN.com

Introduction

LeetCode 314: Binary Tree Vertical Order Traversal asks you to traverse a binary tree in a way that outputs the nodes in a vertical order. The vertical order of a binary tree is determined by the horizontal distance of each node from the root. Nodes with the same horizontal distance are grouped together. The task is to return the nodes in vertical order starting from the leftmost vertical line.

This problem can be solved using breadth-first search (BFS), and it requires careful tracking of the horizontal distance of each node.

Problem Statement

Given the root of a binary tree, return the vertical order traversal of its nodes' values.

For each node at position (i, j), i is the horizontal distance from the root, and j is the level of the node.

Input:

• A binary tree represented by the root node.

Output:

• A list of lists of node values representing the vertical order traversal.

Example

python

# Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[9], [3, 15], [20], [7]]

# Example 2
Input: root = [1,2,3,4,5,6,7]
Output: [[4], [2], [1, 5, 6], [3], [7]]

# Example 3
Input: root = [1]
Output: [[1]]

Step-by-Step Solution

🧠 Intuition

To solve this problem, we need to process the nodes column by column. Each node has a "horizontal distance" (HD) from the root:

• The root starts at HD = 0.
• Nodes to the left of the root have negative HD values.
• Nodes to the right of the root have positive HD values.

For a node at position (i, j), its HD is tracked, and it is placed in the corresponding column (based on HD) as we traverse the tree. To ensure the correct order, we will use a breadth-first search (BFS) approach while maintaining the HD of each node.

✅ Approach

1. Horizontal Distance (HD):
2. Use a queue for BFS, where each element in the queue is a tuple containing the current node and its associated HD. The HD is used to determine the column to which the node belongs.
3. BFS Traversal:
4. Start with the root node (HD = 0). For each node, add its left child with HD - 1 and its right child with HD + 1 to the queue.
5. Tracking Columns:
6. Use a dictionary to map each HD to a list of nodes that have that HD. As we process each node, append it to the corresponding list based on its HD.
7. Result Formation:
8. After processing all nodes, sort the keys of the dictionary to ensure that the columns are in left-to-right order of HD. Then, collect the nodes from the dictionary in the correct order.

✅ Python Code

python

from collections import deque, defaultdict

class Solution:
    def verticalOrder(self, root: TreeNode) -> list[list[int]]:
        if not root:
            return []
        
        # Dictionary to store nodes by their horizontal distance (HD)
        column_table = defaultdict(list)
        
        # Queue for BFS: stores pairs (node, HD)
        queue = deque([(root, 0)])
        
        # Perform BFS
        while queue:
            node, hd = queue.popleft()
            
            # Append the node's value to the corresponding HD column
            column_table[hd].append(node.val)
            
            # If there's a left child, add it to the queue with HD - 1
            if node.left:
                queue.append((node.left, hd - 1))
            
            # If there's a right child, add it to the queue with HD + 1
            if node.right:
                queue.append((node.right, hd + 1))
        
        # Sort the dictionary keys (HD) and collect the results in order
        sorted_columns = sorted(column_table.keys())
        result = [column_table[hd] for hd in sorted_columns]
        
        return result

Explanation of the Code

1. Base Case:
2. If the root is None, return an empty list because there are no nodes to traverse.
3. Queue Initialization:
4. The queue is initialized with the root node and HD = 0, which represents the starting point for BFS traversal.
5. BFS Traversal:

• For each node, we pop it from the queue and append its value to the list corresponding to its HD in the column_table dictionary.
• The left child is pushed onto the queue with HD - 1, and the right child with HD + 1.

1. Sorting and Result Compilation:
2. After BFS completes, we sort the keys of the dictionary (column_table) to get the columns in left-to-right order based on HD. The final result is a list of lists, where each sublist corresponds to a vertical column of the tree.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(N log N)Space ComplexityO(N)

• Time Complexity:
• The BFS traversal visits each node exactly once, so the time complexity of BFS is O(N), where N is the number of nodes. Sorting the keys of the dictionary adds an additional O(N log N) complexity, where N is the number of unique columns (HD values).
• Space Complexity:
• We use a dictionary to store the vertical columns and a queue for BFS. Both structures require space proportional to the number of nodes, so the space complexity is O(N).

🔍 Edge Cases

1. Empty Tree:
2. If the tree is empty (root = None), the result is an empty list.
3. Single Node:
4. If the tree contains only one node, the result will be [[value]], where value is the node's value.
5. Imbalanced Tree:
6. If the tree is heavily skewed (e.g., a linked list), the vertical order will still be correctly represented by columns with one value.
7. Multiple Nodes at the Same HD:
8. If multiple nodes share the same HD (same vertical column), they will be grouped together in the same list, and their order will be from top to bottom (level-order).

✅ Conclusion

LeetCode 314: Binary Tree Vertical Order Traversal is a problem that requires traversing a binary tree in vertical order. By using breadth-first search (BFS) and keeping track of the horizontal distance (HD) of each node, we can efficiently collect and sort nodes by their HD values to produce the desired output.

This approach ensures we can process nodes in the correct order while maintaining their vertical alignment in the result.