987. Vertical Order Traversal of a Binary Tree
Problem Description
Given the root
of a binary tree, the task is to perform a vertical order traversal. The tree nodes have a position represented by a pair (row, col). For any node, its left child's position is defined by (row + 1, col - 1) and its right child's position is (row + 1, col + 1). The root starts at (0, 0).
The vertical order traversal of a binary tree means we need to generate a list of values from top to bottom, starting at the leftmost column and ending at the rightmost column. It's important to consider that nodes located in the same row and column should be arranged according to their values in ascending order. The result should be a list of lists, where each inner list contains the values of the nodes in a single column of the tree, from left to right.
Flowchart Walkthrough
Let's use the provided algorithm flowchart to determine the appropriate search strategy for solving Leetcode 987, Vertical Order Traversal of a Binary Tree. Here's the analysis following the steps from the Flowchart:
Is it a graph?
- Yes: A binary tree is a special form of a graph where each node has at most two children.
Is it a tree?
- Yes: The problem explicitly mentions that it is a binary tree, which is a type of tree.
Since it is a tree, we proceed with using Depth-First Search (DFS) according to the flowchart.
Conclusion: The flowchart suggests using DFS for this tree structure, which is appropriate for traversing and processing nodes in order to maintain vertical order by using additional data structures (e.g., hash maps) to handle the ordering and level issues.
Intuition
To solve this problem, we can utilize depth-first search (DFS). The goal is to traverse the tree while keeping track of the row and column for each node. This requires a helper function that we can recursively call for the left and right children of each node, updating the row and column values accordingly.
Here's how we break it down:
- Perform DFS starting from the root with the initial position as (0, 0).
- As we traverse each node, we record its value along with its position (row, col) in a list.
- For the left child, we increment the row and decrement the column. For the right child, we increment both the row and column.
- After traversing all nodes, we have a list of tuples, each representing (row, col, value) for a node.
- We then sort this list primarily by columns, then by rows, and finally by node values in case of a tie.
- Iterate over the sorted list to create our answer, grouping nodes by their column value.
The provided solution uses these steps to build a sorted list of nodes, which is then used to output the final vertical order traversal.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Solution Approach
The solution to this problem leverages the Depth-First Search (DFS) algorithm to traverse the tree and collect the necessary information at each node (value, row, and column). The primary data structure used to maintain the node details is a list of tuples called nodes
. As the DFS proceeds, each node is visited, and its details are appended to the nodes
list. Here is the outline of the algorithm:
-
Implement a helper function,
dfs(root, i, j)
whereroot
is the current node,i
is the row, andj
is the column. Whendfs
is called on the root node, the initial values arei = 0
andj = 0
. -
Inside the
dfs
function, check if the current node isNone
. If it is, return immediately as there is nothing to process. -
Append a tuple
(i, j, root.val)
to thenodes
list, representing the current node's information. -
Recurse on the left child of the current node by calling
dfs(root.left, i + 1, j - 1)
and on the right child by callingdfs(root.right, i + 1, j + 1)
.
Once the DFS traversal is complete, all nodes are collected in nodes
with their respective positional information. The next step is to sort the list to prepare for grouping nodes into columns:
- Sort the
nodes
list using a custom sort keylambda x: (x[1], x[0], x[2])
. The sorting order is as follows:- Primary key is
x[1]
, which is the column (j
), as we want to group by columns. - Secondary key is
x[0]
, the row (i
), to ensure top-to-bottom ordering within the same column. - Tertiary key is
x[2]
, the node value, to resolve ties by sorting the node values in ascending order for nodes in the same position.
- Primary key is
Finally, the sorted node information is grouped by their column index and the vertical order traversal is constructed:
-
Initialize an empty list
ans
, which will hold the final vertical order traversal as a list of lists. -
Initialize a variable
prev
to an arbitrary value that is outside the potential range of column indices (e.g.,-2000
) to keep track of the previous column index processed. -
Iterate over the sorted
nodes
list and for each node, check if its column indexj
is different fromprev
. If it is, start a new list inans
to collect values for this new column index. Updateprev
to the current column indexj
. -
Add the current node's value
v
to the last list inans
, corresponding to the current column index.
By the end of this process, ans
will contain lists of node values grouped by column indices, sorted top-to-bottom and by values within each column, which is the final vertical order traversal.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example where we have the following binary tree:
3 / \ 9 20 / \ 15 7
Following the approach:
- We start a DFS with the root node
(3)
which has the initial position(0, 0)
. - The node
(3)
is notNone
, so we add the tuple(0, 0, 3)
to ournodes
list. - We recurse left with the node
(9)
updating the row and column to(1, -1)
and append(1, -1, 9)
tonodes
. - As there is no left or right child for
(9)
, we go back up and then recurse right:- Node
(20)
has a position(1, 1)
and we append(1, 1, 20)
tonodes
. - We now recurse on the left child of
(20)
which is(15)
and is at position(2, 0)
. We append(2, 0, 15)
tonodes
. - Next, we recurse on the right child of
(20)
which is(7)
and is at position(2, 2)
. We append(2, 2, 7)
tonodes
.
- Node
At this point, our nodes
list looks like this:
[(0, 0, 3), (1, -1, 9), (1, 1, 20), (2, 0, 15), (2, 2, 7)]
- We sort the
nodes
list by column, then row, then value:
Sorted nodes
list:
[(1, -1, 9), (0, 0, 3), (2, 0, 15), (1, 1, 20), (2, 2, 7)]
- Next, we group the node values by column:
- For column
-1
, we have[9]
. - For column
0
, we have[3,15]
sorted by row. - For column
1
, we have[20]
. - For column
2
, we have[7]
.
- With our
prev
variable keeping track of the current column, we iterate through the sortednodes
and assemble our answer:
ans = [[9], [3,15], [20], [7]]
Thus, the final vertical order traversal is [[9], [3,15], [20], [7]]
, which reflects the values from left to right and top to bottom as required.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.left = left
6 self.right = right
7
8class Solution:
9 def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
10 # Traverse the tree and store each node's value along with its position (level and vertical distance from root)
11 def dfs(node, level, vertical_distance):
12 if not node:
13 return
14 nodes.append((level, vertical_distance, node.val))
15 dfs(node.left, level + 1, vertical_distance - 1) # Traverse left with increased level and decreased vertical distance
16 dfs(node.right, level + 1, vertical_distance + 1) # Traverse right with increased level and increased vertical distance
17
18 nodes = []
19 dfs(root, 0, 0)
20
21 # Sort the nodes firstly by vertical distance, then by level, and finally by the node's value
22 nodes.sort(key=lambda x: (x[1], x[0], x[2]))
23
24 # Group the nodes by their vertical distance
25 result = []
26 prev_vertical_distance = float('-inf') # Initialize with negative infinity (to ensure the first vertical distance is different)
27
28 for level, vertical_distance, value in nodes:
29 if prev_vertical_distance != vertical_distance:
30 # Start a new grouping when the vertical distance changes
31 result.append([])
32 prev_vertical_distance = vertical_distance
33 result[-1].append(value) # Add the current node's value to the current vertical grouping
34
35 return result
36
1class Solution {
2 // Helper method to perform depth-first search (DFS).
3 private void dfs(TreeNode node, int column, int row, List<int[]> nodes) {
4 if (node == null) {
5 return; // Base case: if the node is null, then just return.
6 }
7 // Add the current node's data as a tuple (column, row, value) to the nodes list.
8 nodes.add(new int[]{column, row, node.val});
9 // Continue DFS on the left subtree, decrementing column and row for left traversal.
10 dfs(node.left, column - 1, row - 1, nodes);
11 // Continue DFS on the right subtree, incrementing column and decrementing row for right traversal.
12 dfs(node.right, column + 1, row - 1, nodes);
13 }
14
15 public List<List<Integer>> verticalTraversal(TreeNode root) {
16 List<int[]> nodes = new ArrayList<>(); // List to hold nodes data (column, row, value).
17 dfs(root, 0, 0, nodes); // Start DFS with the root node at column 0, row 0.
18
19 // Sort the list of nodes based on their column, row and value.
20 nodes.sort(new Comparator<int[]>() {
21 @Override
22 public int compare(int[] node1, int[] node2) {
23 // Primary sort by column (x-axis).
24 if (node1[0] != node2[0]) return Integer.compare(node1[0], node2[0]);
25 // Secondary sort by row (y-axis) in descending order.
26 if (node1[1] != node2[1]) return Integer.compare(node2[1], node1[1]);
27 // Tertiary sort by value.
28 return Integer.compare(node1[2], node2[2]);
29 }
30 });
31
32 List<List<Integer>> result = new ArrayList<>(); // Initialize the result list.
33 int previousColumn = Integer.MIN_VALUE; // Variable to track the previous column index.
34
35 for (int[] currentNode : nodes) {
36 // Check if the current node's column index is different than the previous column's.
37 if (previousColumn != currentNode[0]) {
38 // If so, add a new list to the result since we've moved to a new column.
39 result.add(new ArrayList<>());
40 previousColumn = currentNode[0]; // Update the previous column index.
41 }
42 // Add the current node's value to the last list in the result. This list corresponds
43 // to the current column we are populating.
44 result.get(result.size() - 1).add(currentNode[2]);
45 }
46 return result; // Return the list of lists representing vertical order traversal.
47 }
48}
49
50// Define the TreeNode class as it is not provided.
51class TreeNode {
52 int val;
53 TreeNode left;
54 TreeNode right;
55
56 TreeNode() {}
57
58 TreeNode(int val) { this.val = val; }
59
60 TreeNode(int val, TreeNode left, TreeNode right) {
61 this.val = val;
62 this.left = left;
63 this.right = right;
64 }
65}
66
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5// Definition for a binary tree node.
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
11 : val(val), left(left), right(right) {}
12};
13
14/**
15 * Compares two node information tuples for sorting.
16 * @param const vector<int>& a - Node information tuple for the first node.
17 * @param const vector<int>& b - Node information tuple for the second node.
18 * @returns int - The order for sort.
19 */
20int nodeComparator(const vector<int>& a, const vector<int>& b) {
21 if(a[2] != b[2]) return a[2] - b[2];
22 if(a[1] != b[1]) return a[1] - b[1];
23 return a[0] - b[0];
24}
25
26/**
27 * Performs depth-first search on the binary tree to populate the nodes by vertical order.
28 * @param TreeNode* node - The current node being visited.
29 * @param int depth - The depth of the current node.
30 * @param int vertical - The vertical index of the current node used for sorting.
31 * @param vector<vector<int>>& nodes - The array storing node information for sorting.
32 */
33void depthFirstSearch(TreeNode* node, int depth, int vertical, vector<vector<int>>& nodes) {
34 if(!node) return;
35 nodes.push_back({node->val, depth, vertical});
36 depthFirstSearch(node->left, depth + 1, vertical - 1, nodes);
37 depthFirstSearch(node->right, depth + 1, vertical + 1, nodes);
38}
39
40/**
41 * Traverses a binary tree vertically and stores each node in a number array.
42 * @param TreeNode* root - Root of the binary tree.
43 * @returns vector<vector<int>> - 2D array with nodes arranged in vertical order.
44 */
45vector<vector<int>> verticalTraversal(TreeNode* root) {
46 vector<vector<int>> nodes;
47 depthFirstSearch(root, 0, 0, nodes);
48 sort(nodes.begin(), nodes.end(), nodeComparator);
49
50 vector<vector<int>> verticalOrder;
51 int previousIndex = INT_MIN;
52
53 for(auto& node : nodes) {
54 if(node[2] != previousIndex) {
55 verticalOrder.push_back({});
56 previousIndex = node[2];
57 }
58 verticalOrder.back().push_back(node[0]);
59 }
60
61 return verticalOrder;
62}
63
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 val: number
6 left: TreeNode | null
7 right: TreeNode | null
8 constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
9 this.val = (val === undefined ? 0 : val)
10 this.left = (left === undefined ? null : left)
11 this.right = (right === undefined ? null : right)
12 }
13}
14
15/**
16 * Traverses a binary tree vertically and stores each node in a number array.
17 * @param {TreeNode | null} root - Root of the binary tree.
18 * @returns {number[][]} - 2D array with nodes arranged in vertical order.
19 */
20function verticalTraversal(root: TreeNode | null): number[][] {
21 let nodesGroupedByVertical = [];
22 depthFirstSearch(root, 0, 0, nodesGroupedByVertical);
23 nodesGroupedByVertical.sort(nodeComparator);
24
25 let verticalOrder = [];
26 let previousIndex = Number.MIN_SAFE_INTEGER;
27
28 // Group sorted nodes into subarrays based on their vertical index
29 for (let node of nodesGroupedByVertical) {
30 const [nodeValue, , verticalIndex] = node;
31 if (verticalIndex !== previousIndex) {
32 verticalOrder.push([]);
33 previousIndex = verticalIndex;
34 }
35 verticalOrder[verticalOrder.length - 1].push(nodeValue);
36 }
37 return verticalOrder;
38}
39
40/**
41 * Compares two node information arrays for sorting.
42 * @param {Array<number>} a - Node information array for the first node.
43 * @param {Array<number>} b - Node information array for the second node.
44 * @returns {number} - The order for sort.
45 */
46function nodeComparator(a: Array<number>, b: Array<number>): number {
47 const [valueA, depthA, indexA] = a;
48 const [valueB, depthB, indexB] = b;
49
50 if (indexA === indexB) {
51 if (depthA === depthB) {
52 return valueA - valueB;
53 }
54 return depthA - depthB;
55 }
56 return indexA - indexB;
57}
58
59/**