987. Vertical Order Traversal of a Binary Tree (HARD)

Intro

This is a hard problem on Leetcode. This is an interesting twist to the usual traversal problems with an acceptance rating of 47%

Problem Statement

Given the root of a binary tree, we have to calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

What is vertical order traversal

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

So given a binary tree that looks like

The left most node is 9 and the right most node is 7. The top most node(aka root) is 3 and there are two nodes that would be considered bottom most, 15 and 7.

Since in vertical order traversal, we do top to bottom and left to right. The return value will look like [[9],[3,15],[20],[7]].

Solution

A good way to solve this would be to do a DFS(depth first search). I chose to do this recursively. We can also do this iteratively, which we will cover later.

In order to solve this, we have to divide the problem in two parts.

• Figuring out which node goes into what column and rows
• Putting all the nodes together in the vertical traversal order

The first part can be done by going through the binary tree and the second part is putting it together in the right order.

The first part:

var verticalTraversal = function(root) {
    const columnMap = new Map();

    const dfs = (node, row, col) => {
        if (!node) {
            return;
        }

        if (!columnMap.has(col)) {
            columnMap.set(col, []);
        }
        columnMap.get(col).push({ val: node.val, row });

        dfs(node.left, row + 1, col - 1);
        dfs(node.right, row + 1, col + 1);
    };
    dfs(root, 0, 0);

This is a standard recursive function and it goes through and captures all the nodes by column and also stores its row. You can use a plain object for this as well. The column map will look something like

[
  [ 0, [ [Object], [Object] ] ],
  [ -1, [ [Object] ] ],
  [ 1, [ [Object] ] ],
  [ 2, [ [Object] ] ]
]

Now we know all the nodes and their respective columns and rows. We have to just turn that information into an ordered array of arrays.

    return [...columnMap.entries()].sort((a, b) => a[0] - b[0])
        .map((nodes) => {
            nodes[1].sort((a, b) => a.row !== b.row ? a.row - b.row : a.val - b.val);

            const result = nodes[1].map(node => node.val);
            return result;
        });

There is a lot of things happening here so let's break it down.

First we have the sort function [...columnMap.entries()].sort((a, b) => a[0] - b[0]). It takes all the keyValue pairs, puts them in an array and sorts them by their columns(keys).

Then we have the massive map function. There are three parts to this.

1) The main map: We have to mmap through the large key + array of objects and turn it into a simple array of arrays. We are working through each value pair and running the the sort and the map on the values.

2) The sort function makes sure that the nodes are in the vertical traversal order. Sort the nodes by rows and values

3) the map gets rid of all values about the node except the nodeValue. puts it in an array and returns it to the bigger arr.

at the end of this, you will have all the information need for this problem

There are other solutions like doing BFS iteratively and many other variations. This was my favorite because I feel like it is as efficient as most of them, but it is very simple and straight forward

Thanks for reading. Hope it helps!