Vertical Order Traversal of a Binary Tree

Leetcode#987

Problem:

Vertical Order Traversal of a Binary Tree - LeetCode

“Hi, There”, this problem is based on the Binary tree and PriorityQueue.

Approach:

Here will insert the tree data into the map of PriorityQueues with rows and columns vertically. So while polling the elements from PriorityQueue it will pop out the elements from the leftmost column to towards right vertically.

1. Break the tree into rows and columns as explained in the problem.

Fig-1

2. Now let’s convert the above diagram by pushing it into the nested Map (with TreeMap & Priority Queue) which holds, row, columns, and row-column-wise data. i.e

Fig-2

If you observe Fig-1 & Fig-2, We are constructing the map using BFS traversal i.e row by row from the given tree.

3. Now after constructing the Map we can iterate it and poll the elements from the PriorityQueue (MinHeap by default).

Here PriorityQueue will give us traversing from the left-most column. (-2) to right most (2) vertically.

so the column order vs values :

[-2, -1, 0, 1,2 ]← — — — — — — → [[4],[2],[1,5,6],[3],[7]]

which is a required Output.

Java Implementation:

O/P:

Thanks for your read and 👏👏

Will see you in the next read.

#arraysinjava. #array #tree #graph #linkedlist #Queue

#datastructures #codinginterviewquestions #codinginterview #faang #leetcode #animated #java #python #faang #motion