Leetcode Daily - Vertical Order Traversal Of Binary Tree

Leetcode Daily - August 7, 2020

Vertical Order Traversal Of Binary Tree

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

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

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

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

Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);

The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]

Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Notes:

• The tree will have between 1 and 1000 nodes.
• Each node's value will be between 0 and 1000.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS or BFS

(Submission - Accepted)

Based on the detailed instructions, I understand that each node will have its own X and Y coordinate (relative to the root node's). With this understanding, I used depth first search to search the binary tree and add each node to a data structure. I used a Javascript object, which has hash table characteristics, to hold data about each node.

Since we need to return a data structure which sorts the nodes by X value, I decided to sort them by the X value when I add them to the container.

I wanted my container to look something like this after it's been filled in (using Example 1's values):

 const xCoordMap = {
   "-1": [{val:9, y:-1}],
   "0": [{val:3, y:0}, {val:15, y:-2}],
   "1": [{val:20, y:1}],
   "2": [{val:7, y:2}]
 }

Originally I tried to use breadth first search because that search algorithm searches through all the nodes of the same Y level consecutively. However, when there is a tie in Y value, the question wants the lower node value to be placed first. So I ended up recording the Y values in order to detect ties, and then sorted them first by highest Y value and then by lowest value (if the Y values are tied).

Submitted Javascript code:

var verticalTraversal = function(root) {
    // dfs or bfs but calculate the coordinates while running it 
    // using bfs we won't have to use the Y values to sort (?)
    // left goes to X-1, Y-1, right goes to X+1, Y-1 
    let stack = [{...root, x: 0, y:0}];

    let xCoordMap = {}

    const addNode = (val, x, y) => {
        // if the key, 'x', already exists, push it 
        // if it doesn't, make a new array 
        if (xCoordMap[`${x}`]) {
            xCoordMap[`${x}`].push({val, y});
        } else {
            xCoordMap[`${x}`] = [{val, y}];
        }
    }


    while (stack.length > 0) {

        const currNode = stack.pop();

        addNode(currNode.val, currNode.x, currNode.y);

        if (currNode.left) {
            stack.push({...currNode.left, x: currNode.x - 1, y: currNode.y - 1});
        }

        if (currNode.right) {
            stack.push({...currNode.right, x: currNode.x + 1, y: currNode.y - 1});
        }

    }

    // we have an object with numbered keys and arrays of values 
    const sortedKeys = Object.keys(xCoordMap).sort((a,b) => Number(a) - Number(b));
    const vertArrays = sortedKeys.map(key => {
       // sort the array then return it with only vals, not x and y 
       // sort by y first, then by value if y's are the same 
       xCoordMap[key].sort((a,b) => b.y - a.y).sort((a,b) => {
           if (a.y === b.y) return a.val - b.val;
           return 0;
       })
       return xCoordMap[key].map(obj => obj.val);
    });
    return vertArrays;
};

Discussion and Conclusions

I really focused on putting node data into a data structure and sorting it by the X value right when it is added. I felt that this is faster than any method which searches first and then sorts later. Especially because I am using a hash table to store the nodes with the same X value.

However, I could've done some more thinking on sorting the arrays of my node container by the Y value and node value upon adding, instead of before returning. I believe I could've done it in O(n) if I tried to put new nodes in the right spot when adding them, instead of the O(nlog(n)) sorting that I did to return the solution.