Binary Tree Vertical Order Traversal

Given the root of a binary tree, return the vertical order traversal of its nodes' values.

(i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: [[9],[3,15],[20],[7]]

Example 2:

Input: root = [3,9,8,4,0,1,7]

Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]

Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Constraints:

The number of nodes in the tree is in the range [0, 100].

-100 ≤ Node.val ≤ 100

Solution:-

This is yet another problem about Binary Tree traversals.

As one would probably know, the common strategies to traverse a Tree data structure are Breadth-First Search (a.k.a BFS) and Depth-First Search (a.k.a. DFS).

The DFS strategy can be further distinguished as preorder DFS, inorder DFS and postorder DFS, depending on the relative order of visit among the node itself and its child nodes.

If one is not familiar with the concepts of BFS and DFS, one can find the corresponding problems on LeetCode to practice with.

Also, we have an Explore card called Queue & Stack where we cover both the BFS traversal as well as the DFS traversal.

Hence, in this article, we won't repeat ourselves on these concepts.

In the problem description, we are asked to return the vertical order of a binary tree, which actually implies two sub-orders, where each node would have a 2-dimensional index (denoted as <column, row >)

column-wise order:-

If we look at a binary tree horizontally, each node can be aligned to a specific column, based on its relative offset to the root node of the tree.

Let us assume that the root node has a column index of 0, then its left child node would have a column index of -1 and its right child node would have a column index of +1, and so on.

row-wise order:-

Now if we put the nodes into a vertical dimension, each node would be assigned to a specific row, based on its level (i.e. the vertical distance to the root node).

Let us assume that the root node has a row index of 0, then both its child nodes would have the row index of 1.

Given the above definitions, we can now formulate the problem as a task to order the nodes based on the 2-dimensional coordinates that we defined above.

More specifically, the nodes should be ordered by column first, and further the nodes on the same column should be ordered vertically based on their row indices.

Approach 1: Breadth-First Search (BFS)

With the formulation of the problem in the overview section, one of the most intuitive solutions to tackle the problem would be applying the BFS traversal, where the nodes would be visited level by level.

With the BFS traversal, we naturally can guarantee the vertical order of the visits, i.e. the nodes at higher levels (large row values) would get visited later than the ones at lower levels.

However, we are still missing the horizontal order ( the column order). To ensure this order, we need to do some additional processing during the BFS traversal.

The idea is that we keep a hash table (let's denote it as columnTable<key, value>), where we keep the node values grouped by the column index.

The key in the hash table would be the column index, and the corresponding value would be a list which contains the values of all the nodes that share the same column index.

In addition, the values in the corresponding list should be ordered by their row indices, which would be guaranteed by the BFS traversal as we mentioned before.

Algorithm:-

We elaborate on the steps to implement the above idea.

First, we create a hash table named columnTable to keep track of the results.

As to the BFS traversal, a common code pattern would be to use a queue data structure to keep track of the order we need to visit nodes.

We initialize the queue by putting the root node along with its column index value (0).

We then run the BFS traversal with a loop consuming the elements from the queue.

At each iteration within the BFS, we pop out an element from the queue.

The element consists of a node and its corresponding column index.

If the node is not empty, we then populate the columnTable with the value of the node.

Subsequently, we then put its child nodes along with their respective column indices (i.e. column-1 and column+1) into the queue.

At the end of the BFS traversal, we obtain a hash table that contains the desired node values grouped by their column indices.

For each group of values, they are further ordered by their row indices.

We then sort the hash table by its keys, i.e. column index in ascending order. And finally we return the results column by column.

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  class Solution {
    public List	<List	<Integer	>	> verticalOrder(TreeNode root) {
      List	<List	<Integer	>	> output = new ArrayList();
      if (root == null) {
        return output;
      }

      Map	<Integer, ArrayList	> columnTable = new HashMap();
      Queue	<Pair	<TreeNode, Integer	>	> queue = new ArrayDeque();
      int column = 0;
      queue.offer(new Pair(root, column));

      while (!queue.isEmpty()) {
        Pair	<TreeNode, Integer	> p = queue.poll();
        root = p.getKey();
        column = p.getValue();

        if (root != null) {
          if (!columnTable.containsKey(column)) {
            columnTable.put(column, new ArrayList	<Integer	>());
          }
          columnTable.get(column).add(root.val);

          queue.offer(new Pair(root.left, column - 1));
          queue.offer(new Pair(root.right, column + 1));
        }
      }

      List	<Integer	> sortedKeys = new ArrayList	<Integer	>(columnTable.keySet());
      Collections.sort(sortedKeys);
      for(int k : sortedKeys) {
        output.add(columnTable.get(k));
      }

      return output;
    }
  }
  
  

Complexity Analysis

Time Complexity: log⁡ O(N*logN) where N is the number of nodes in the tree.

In the first part of the algorithm, we do the BFS traversal, whose time complexity is O(N) since we traversed each node once and only once.

In the second part, in order to return the ordered results, we then sort the obtained hash table by its keys, which could result in the (log⁡)O(NlogN) time complexity in the worst case scenario where the binary tree is extremely imbalanced (for instance, each node has only left child node.)

As a result, the overall time complexity of the algorithm would be log⁡ O(N*logN).

Space Complexity: O(N) where N is the number of nodes in the tree.

First of all, we use a hash table to group the nodes with the same column index.

The hash table consists of keys and values.

In any case, the values would consume O(N) memory.

While the space for the keys could vary, in the worst case, each node has a unique column index, i.e. there would be as many keys as the values.

Hence, the total space complexity for the hash table would still be O(N).

During the BFS traversal, we use a queue data structure to keep track of the next nodes to visit.

At any given moment, the queue would hold no more two levels of nodes.

For a binary tree, the maximum number of nodes at a level would be +122N+1

which is also the number of leafs in a full binary tree.

As a result, in the worst case, our queue would consume at most (+12⋅2)=O(2*N+1​⋅2)=O(N) space.

Lastly, we also need some space to hold the results, which is basically a reordered hash table of size O(N) as we discussed before.

To sum up, the overall space complexity of our algorithm would be O(N).