987. Vertical Order Traversal of a Binary Tree

HardTreeDepth-First SearchBreadth-First SearchHash TableBinary Tree
Leetcode Link

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.

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:

  1. Perform DFS starting from the root with the initial position as (0, 0).
  2. As we traverse each node, we record its value along with its position (row, col) in a list.
  3. For the left child, we increment the row and decrement the column. For the right child, we increment both the row and column.
  4. After traversing all nodes, we have a list of tuples, each representing (row, col, value) for a node.
  5. We then sort this list primarily by columns, then by rows, and finally by node values in case of a tie.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

In a binary min heap, the minimum element can be found in:

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:

  1. 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.

  2. Inside the dfs function, check if the current node is None. If it is, return immediately as there is nothing to process.

  3. Append a tuple (i, j, root.val) to the nodes list, representing the current node's information.

  4. 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:

  1. 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:

  1. Initialize an empty list ans, which will hold the final vertical order traversal as a list of lists.

  2. 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.

  3. 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.

  4. 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.

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

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

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

1     3
2    / \
3   9   20
4      /  \
5     15   7

Following the approach:

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

1[(0, 0, 3), (1, -1, 9), (1, 1, 20), (2, 0, 15), (2, 2, 7)]
  1. We sort the nodes list by column, then row, then value:

Sorted nodes list:

1[(1, -1, 9), (0, 0, 3), (2, 0, 15), (1, 1, 20), (2, 2, 7)]
  1. 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].
  1. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following problems can be solved with backtracking (select multiple)

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:

  1. 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.

  2. 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).

  3. 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:

  1. 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).

  2. 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.

  3. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ