987. Vertical Order Traversal of a Binary Tree

HardTreeDepth-First SearchBreadth-First SearchHash TableBinary 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) where root is the current node, i is the row, and j is the column. When dfs is called on the root node, the initial values are i = 0 and j = 0.
Inside the dfs function, check if the current node is None. If it is, return immediately as there is nothing to process.
Append a tuple (i, j, root.val) to the nodes 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 calling dfs(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 key lambda 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.

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 index j is different from prev. If it is, start a new list in ans to collect values for this new column index. Update prev to the current column index j.
Add the current node's value v to the last list in ans, 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 Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example where we have the following binary tree:

Following the approach:

We start a DFS with the root node (3) which has the initial position (0, 0).
The node (3) is not None, so we add the tuple (0, 0, 3) to our nodes list.
We recurse left with the node (9) updating the row and column to (1, -1) and append (1, -1, 9) to nodes.
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) to nodes.
- We now recurse on the left child of (20) which is (15) and is at position (2, 0). We append (2, 0, 15) to nodes.
- Next, we recurse on the right child of (20) which is (7) and is at position (2, 2). We append (2, 2, 7) to nodes.

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 sorted nodes 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/**
60 * Performs depth-first search on the binary tree to populate the solution array.
61 * @param {TreeNode | null} node - The current node being visited.
62 * @param {number} depth - The depth of the current node.
63 * @param {number} verticalIndex - The vertical index of the current node used for sorting.
64 * @param {Array<Array<number>>} solution - The array storing node information for sorting.
65 */
66function depthFirstSearch(node: TreeNode | null, depth: number, verticalIndex: number, solution: Array<Array<number>>): void {
67  if (!node) return;
68
69  solution.push([node.val, depth, verticalIndex]);
70
71  // Traverse the left subtree
72  depthFirstSearch(node.left, depth + 1, verticalIndex - 1, solution);
73  // Traverse the right subtree
74  depthFirstSearch(node.right, depth + 1, verticalIndex + 1, solution);
75}
76

Time and Space Complexity

The given code performs a vertical traversal of a binary tree. Let's analyze both the time complexity and space complexity:

Time Complexity:

The dfs function is a depth-first traversal of the binary tree. It visits each node exactly once, which results in a time complexity of O(N) where N is the number of nodes in the tree.
The sort function is then called on the list of nodes, where the list length is equal to the number of nodes, N. Python's Timsort algorithm is used, which has a worst-case complexity of O(NlogN).
The final loop runs through all nodes once more to group them by their vertical positions. This has a time complexity of O(N).

Considering all the above, the overall time complexity is dominated by the sorting step, which is O(NlogN).

Space Complexity:

The nodes list holds all nodes in the tree with their corresponding row and column indexes. Therefore, it has a space complexity of O(N).
The space required by the depth-first search stack is proportional to the height of the tree, at worst O(N) in the case of a skewed tree.
The ans list that is used to store the final output has a space complexity of O(N) since it holds all values in the nodes list.

Given the list and recursion stack, the overall space complexity is O(N).

Thus, the time complexity of the code is O(NlogN) and the space complexity is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know