Given the root
of a binary tree, calculate the vertical order traversal of the binary tree.
For each node at position (row, col)
, its left and right children will be at positions (row + 1, col - 1)
and (row + 1, col + 1)
respectively. The root of the tree is at (0, 0)
.
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Consider the following binary tree:
3
/ \
9 20
/ \
15 7
The vertical order traversal would be: [[9], [3, 15], [20], [7]]
Example 2:
Consider the following binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
The vertical order traversal would be: [[4], [2], [1, 5, 6], [3], [7]]
Clarifications:
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:
The brute force method for vertical order traversal of a binary tree essentially tries to capture every single node and its horizontal position. It then organizes them based on these horizontal positions. It is an exhaustive approach that doesn't take any shortcuts.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def vertical_order_traversal_brute_force(root):
node_levels = []
def calculate_node_levels(node, level):
if not node:
return
node_levels.append((level, node.val))
calculate_node_levels(node.left, level - 1)
calculate_node_levels(node.right, level + 1)
calculate_node_levels(root, 0)
# Need this to determine what range of levels to iterate through.
if not node_levels:
return []
min_level = min(level for level, _ in node_levels)
max_level = max(level for level, _ in node_levels)
vertical_order = []
# Iterate through each horizontal level
for level in range(min_level, max_level + 1):
current_level_nodes = []
# Collect nodes at the current horizontal level
for node_level, node_value in node_levels:
if node_level == level:
current_level_nodes.append(node_value)
vertical_order.append(current_level_nodes)
return vertical_order
The key to solving this problem efficiently is to think about the tree's structure in terms of columns. We want to group nodes by their horizontal distance from the root and then order those groups by level.
Here's how the algorithm would work step-by-step:
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def vertical_order(root):
if not root:
return []
column_to_nodes = {}
queue = deque([(root, 0)])
while queue:
node, column_index = queue.popleft()
# Store the node value for the current column index.
if column_index not in column_to_nodes:
column_to_nodes[column_index] = []
column_to_nodes[column_index].append(node.val)
if node.left:
queue.append((node.left, column_index - 1))
if node.right:
queue.append((node.right, column_index + 1))
# Get column indexes in sorted order.
sorted_columns = sorted(column_to_nodes.keys())
result = []
# Construct the final result based on the sorted column indexes.
for column_index in sorted_columns:
result.append(column_to_nodes[column_index])
return result
Case | How to Handle |
---|---|
Null or Empty Tree | Return an empty list if the root is null, as there are no nodes to traverse. |
Single Node Tree | Return a list containing a list with the root node's value, representing the single column. |
Tree with all nodes having the same value | The algorithm should correctly assign columns and row to nodes with same value ensuring proper vertical order. |
Highly skewed tree (e.g., all nodes on the left) | The algorithm should correctly handle unbalanced trees without stack overflow or performance issues. |
Large tree (potential memory issues) | Consider using an iterative approach or a space-efficient data structure to prevent excessive memory consumption for large trees. |
Negative node values | The algorithm should handle negative node values without any issues. |
Nodes with zero value | The algorithm should handle zero values for nodes without issues. |
Integer Overflow with column indices | Use appropriate data types (e.g., long) for column indices to prevent potential integer overflows, especially in very wide trees. |