Vertical Order Traversal of a Binary Tree
Given the root of a binary tree, calculate the vertical order traversal. The traversal organizes nodes by their vertical positions. Nodes in the same column and row are sorted by value.
Approach
We utilize a combination of Breadth-First Search (BFS) and a nested data structure (TreeMap) to store nodes by their coordinates efficiently. The steps are:
- Traverse the tree using BFS while keeping track of each node's row and column.
- Store nodes in a nested
TreeMap, ensuring columns and rows are sorted. - Sort nodes in the same position by their values and build the result.
Code Implementation
class Tuple {
TreeNode node;
int row, col;
public Tuple(TreeNode node, int row, int col) {
this.node = node;
this.row = row;
this.col = col;
}
}
class Solution {
public List> verticalTraversal(TreeNode root) {
TreeMap>> map = new TreeMap<>();
Queue queue = new LinkedList<>();
queue.offer(new Tuple(root, 0, 0));
while (!queue.isEmpty()) {
Tuple t = queue.poll();
TreeNode node = t.node;
int row = t.row, col = t.col;
map.putIfAbsent(col, new TreeMap<>());
map.get(col).putIfAbsent(row, new PriorityQueue<>());
map.get(col).get(row).offer(node.val);
if (node.left != null) queue.offer(new Tuple(node.left, row + 1, col - 1));
if (node.right != null) queue.offer(new Tuple(node.right, row + 1, col + 1));
}
List> result = new ArrayList<>();
for (TreeMap> rows : map.values()) {
List column = new ArrayList<>();
for (PriorityQueue nodes : rows.values()) {
while (!nodes.isEmpty()) column.add(nodes.poll());
}
result.add(column);
}
return result;
}
}
Complexity Analysis
Time Complexity: O(n log n), where n is the number of nodes (due to sorting).
Space Complexity: O(n), for storing the tree structure in the map.
Vertical Order Traversal of a Binary Tree
The problem of Vertical Order Traversal of a Binary Tree combines the concepts of binary tree traversal and coordinate-based sorting. It is widely used in various tree visualization and transformation algorithms.
Problem Statement
Given the root of a binary tree, the goal is to return the vertical order traversal of its nodes' values. In this traversal, nodes are grouped by their vertical columns, sorted by their row positions, and further sorted by values when ties occur.
Specifically:
- Each node in the binary tree is assigned a coordinate:
(row, column). - The left child of a node at
(row, col)is located at(row + 1, col - 1). - The right child is located at
(row + 1, col + 1). - The vertical order of traversal groups nodes with the same column index, sorted by row and value.
Approach to Solve the Problem
To efficiently implement vertical order traversal, we can use one of the following approaches:
1. Breadth-First Search (BFS)
This method uses a queue to perform a level-order traversal while keeping track of the coordinates of each node.
- Start with the root node at
(0, 0)and enqueue it. - Dequeue nodes one by one, storing their values along with their coordinates in a map.
- Group nodes by column index and sort them by row and value.
2. Depth-First Search (DFS)
In the DFS approach, we recursively traverse the tree while passing the current coordinates as parameters.
- For each node, record its value and coordinates in a map.
- Visit the left and right children with updated coordinates.
- Finally, sort the map by column, row, and value.
3. Optimized Coordinate Tracking
Using advanced data structures such as a sorted map or a min-heap allows for efficient grouping and sorting of nodes during traversal.
Implementation
Here is a Python implementation of the BFS-based approach:
from collections import defaultdict, deque
def verticalTraversal(root):
# Map to store nodes grouped by column
column_map = defaultdict(list)
# Queue to perform BFS, storing nodes and their coordinates
queue = deque([(root, 0, 0)]) # (node, row, column)
while queue:
node, row, col = queue.popleft()
if node:
column_map[col].append((row, node.val))
queue.append((node.left, row + 1, col - 1))
queue.append((node.right, row + 1, col + 1))
# Sort columns and their values
sorted_columns = sorted(column_map.keys())
result = []
for col in sorted_columns:
column_nodes = sorted(column_map[col], key=lambda x: (x[0], x[1]))
result.append([val for _, val in column_nodes])
return result
Here is the Java implementation using DFS:
import java.util.*;
class Solution {
Map> columnMap = new TreeMap<>();
public List> verticalTraversal(TreeNode root) {
dfs(root, 0, 0);
List> result = new ArrayList<>();
for (List values : columnMap.values()) {
values.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
List sortedColumn = new ArrayList<>();
for (int[] value : values) {
sortedColumn.add(value[1]);
}
result.add(sortedColumn);
}
return result;
}
private void dfs(TreeNode node, int row, int col) {
if (node == null) return;
columnMap.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
dfs(node.left, row + 1, col - 1);
dfs(node.right, row + 1, col + 1);
}
}
Example
Consider the binary tree:
Tree Structure:
3
/ \
9 20
/ \
15 7
The vertical order traversal for this tree is:
[ [9], [3, 15], [20], [7] ]
Complexity Analysis
Time Complexity: O(n log n), where n is the number of nodes. Sorting the nodes by column adds logarithmic overhead.
Space Complexity: O(n), due to the storage required for the map and the recursion stack (in the case of DFS).
Applications
- Tree visualization and rendering in GUIs.
- Problems that require coordinate-based traversal of data structures.
- Analyzing spatial relationships in hierarchical data.
Conclusion
Vertical Order Traversal of a Binary Tree is a versatile problem that demonstrates the integration of traversal techniques and sorting. It is an excellent exercise for mastering tree algorithms and understanding spatial relationships in hierarchical data structures.
Explore variations of this problem by incorporating additional constraints, such as custom sorting orders or multi-branch trees, to deepen your understanding.
Vertical Order Traversal of a Binary Tree is a significant problem that highlights tree traversal techniques combined with coordinate-based sorting. It requires organizing nodes column-wise and sorting them based on their positions.
Problem Statement:
Given the root of a binary tree, perform a vertical order traversal. Each node's position is determined by its depth (row) and horizontal alignment (column). The rules for positioning are as follows:
- The left child of a node at
(row, col)is positioned at(row + 1, col - 1). - The right child of a node at
(row, col)is positioned at(row + 1, col + 1).
Further details and explanation continue here... Let me know if you'd like me to elaborate!
