
Problem Statement
In computational tree theory, vertical order traversal refers to an operation on binary trees where the nodes are visited in a columnar format. Specifically, given a binary tree, we must list the nodes by their columns from left to right. Each node is defined by a coordinate (row, col)
, where the root node resides at (0, 0)
. The left child of a node moves one row down and one column to the left (row + 1, col - 1)
, and the right child moves one row down and one column to the right (row + 1, col + 1)
.
During the traversal, if multiple nodes occupy the same coordinate, they are to be sorted by their values before listing. The challenge is to calculate and return the vertical order of nodes for each column in the binary tree.
Examples
Example 1
Input:
root = [3,9,20,null,null,15,7]
Output:
[[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.
Example 2
Input:
root = [1,2,3,4,5,6,7]
Output:
[[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column. Column -1: Only node 2 is in this column. Column 0: Nodes 1, 5, and 6 are in this column. 1 is at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.
Example 3
Input:
root = [1,2,3,4,6,5,7]
Output:
[[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped. Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
Constraints
- The number of nodes in the tree is in the range
[1, 1000]
. 0 <= Node.val <= 1000
Approach and Intuition
Tree Traversal:
- Iterate through the tree nodes using a breadth-first search (BFS), which processes nodes level by level. This ensures nodes are captured in row order.
Tracking Position:
- As each node is processed, record its
(row, col)
position. Use a hash map (columnTable
) to store nodes according to theircol
value. If two nodes share the same column, they are added to the same list within that column's key incolumnTable
.
- As each node is processed, record its
Sorting Within Columns:
- For columns with multiple nodes at the same
(row, col)
coordinate, sort those nodes based on their values. This might require a sorting function within the BFS loop or a post-processing step after all nodes are processed.
- For columns with multiple nodes at the same
Extracting Results:
- After processing all nodes, extract column keys from
columnTable
in sorted order. For each key, the associated values give the vertical order for that column.
- After processing all nodes, extract column keys from
Putting It All Together:
- The resultant list of lists is constructed by iterating through the sorted column keys, gathering and formatting the nodes from
columnTable
according to the problem statement requirements.
- The resultant list of lists is constructed by iterating through the sorted column keys, gathering and formatting the nodes from
Benefits of the Approach
- Compliance with Constraints: Efficient and within acceptable performance bounds for up to 1000 nodes.
- Robustness: BFS ensures correct traversal order and avoids skipped nodes.
- Clarity and Precision: Sorted column processing ensures accurate vertical ordering.
Solutions
- Java
class VerticalOrderTraversal {
Map<Integer, ArrayList<Pair<Integer, Integer>>> colTable = new HashMap<>();
int minimumCol = 0, maximumCol = 0;
private void traverse(TreeNode node, Integer depth, Integer horizontalDist) {
if (node == null)
return;
if (!colTable.containsKey(horizontalDist)) {
this.colTable.put(horizontalDist, new ArrayList<Pair<Integer, Integer>>());
}
this.colTable.get(horizontalDist).add(new Pair<Integer, Integer>(depth, node.val));
this.minimumCol = Math.min(minimumCol, horizontalDist);
this.maximumCol = Math.max(maximumCol, horizontalDist);
// Execute DFS traversal in preorder
this.traverse(node.left, depth + 1, horizontalDist - 1);
this.traverse(node.right, depth + 1, horizontalDist + 1);
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
// 1). Conduct the DFS traversal
this.traverse(root, 0, 0);
// 2). Extract and sort results from the column table
for (int i = minimumCol; i <= maximumCol; ++i) {
// Sort by row and value
Collections.sort(colTable.get(i), new Comparator<Pair<Integer, Integer>>() {
@Override
public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
if (p1.getKey().equals(p2.getKey()))
return p1.getValue() - p2.getValue();
else
return p1.getKey() - p2.getKey();
}
});
List<Integer> sortedCol = new ArrayList<>();
for (Pair<Integer, Integer> p : colTable.get(i)) {
sortedCol.add(p.getValue());
}
result.add(sortedCol);
}
return result;
}
}
The Java implementation provided performs a vertical order traversal of a binary tree. Here is a summary of how it works:
- A
Map<Integer, ArrayList<Pair<Integer, Integer>>>
namedcolTable
stores nodes against their respective horizontal distances. Each node is represented by a pair containing the depth and its value. - The
traverse
method performs a Depth First Search (DFS) on the tree:- It checks if the current node is null, if so, it returns.
- Nodes are stored in
colTable
with their depth and value. - Recursive calls adjust the horizontal distance, moving left (decrementing) and right (incrementing).
- Minimum and maximum columns (
minimumCol
andmaximumCol
) are updated during traversal to keep track of the leftmost and rightmost tree boundaries. - The
verticalOrder
method processes the tree:- Begins with checking if the root is null. If true, returns an empty result.
- Calls
traverse
to fillcolTable
. - Processes entries from
minimumCol
tomaximumCol
, sorting them by depth and value when depths are the same. - The sorted values for each column are aggregated into
result
.
Following these steps ensures that each vertical column from left to right is sorted first by the depth of nodes and then by their values if multiple nodes share the same depth.
Key insights:
- Utilizes DFS and a hashmap with a list to manage sorting and output.
- Ensures accuracy in vertical arrangements by careful tracking and sorting mechanisms.
- Efficiently handles null trees and provides a structured output format.
- Python
class Solution:
def verticalOrder(self, rootNode: TreeNode) -> List[List[int]]:
if rootNode is None:
return []
# Dict to maintain column-wise nodes
colTable = defaultdict(list)
# Initialize column limits
min_col = max_col = 0
def traverse(node, vertical, horizontal):
if node:
nonlocal min_col, max_col
colTable[horizontal].append((vertical, node.val))
min_col = min(min_col, horizontal)
max_col = max(max_col, horizontal)
# Recursive traversals for left and right children
traverse(node.left, vertical + 1, horizontal - 1)
traverse(node.right, vertical + 1, horizontal + 1)
# Start DFS traversal from the root
traverse(rootNode, 0, 0)
# Prepare output list from the colTable
result = []
for column in range(min_col, max_col + 1):
# Sorting the tuples by their row index and then by value
result.append([value for row, value in sorted(colTable[column])])
return result
This solution outlines a method to perform vertical order traversal on a binary tree using Python 3.
- The input node is checked to ensure it is not
None
. If it'sNone
, the function returns an empty list. - A dictionary called
colTable
is initialized usingdefaultdict
of thelist
type to keep track of nodes categorized by their "horizontal distance" from the root. - Two variables,
min_col
andmax_col
, are initialized to0
. They are used to track the smallest and largest horizontal distances that have been encountered in the tree, respectively. - The
traverse
function is a nested function defined to perform a Depth First Search (DFS) traversal of the tree. It accepts:node
: current tree node.vertical
: vertical level of the node.horizontal
: horizontal distance of the node from the root.
- In the
traverse
function:- If the current node exists, the node value and its vertical level are appended to the list in
colTable
that corresponds to its horizontal distance. - Updates are made to
min_col
andmax_col
based on the current node's horizontal position. - The function then recursively calls itself for the left and right children of the current node, adjusting the
vertical
andhorizontal
values as appropriate.
- If the current node exists, the node value and its vertical level are appended to the list in
After the traversal completes, the outputs are collected from colTable
. The results are sorted and appended to the final list result
:
- The result list is constructed by iterating from
min_col
tomax_col
. - For each column, values are sorted, first by row index (
vertical
) and then by node value to maintain the order of nodes as observed in vertical traversal from top to bottom.
This ensures that the final output result
represents the node values in vertical order, where each sublist corresponds to nodes at the same horizontal distance, sorted vertically.
No comments yet.