# Solution For Vertical Order Traversal Of A Binary Tree

Problem statement:

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, 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.

Examples:

Example 1:
Input: [3,9,20,null,null,15,7]

3
/ \
9 20
/ \
15 7

Output:
[
,
[3,15],
,
 ]

Explanation:
– The top-down view of the tree is , [3,15], ,  – In the vertical (column) order traversal, we should first visit the leftmost node (9), then the middle column node (3 and 15), and finally the rightmost node (20 and 7).

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

`````` 1
``````

/ \
2 3
/ \ / \
4 5 6 7

Output:
[
,
,
[1,5,6],
,
 ]

Explanation:
– The top-down view of the tree is , , [1,5,6], ,  – In the vertical (column) order traversal, we should first visit the leftmost node (4), then the left column node (2), then the middle column node (1, 5, and 6), and finally the rightmost node (3 and 7).

Approach:

To solve this problem, we can use map and queue. We can traverse through the tree level by level using a queue and keep track of the columns using a map.

Let’s say we have a current node with value val and column index col. We can add this node’s value to the column in the map with key col.

• For the left child node, we can add its value to the column col-1.
• For the right child node, we can add its value to the column col+1.
• We also need to keep track of the minimum and maximum column index for all nodes in the tree. This will help us in iterating through the map keys to get the columns in order.

After we have added all the nodes to the map, we can iterate through the map from the minimum column index to the maximum column index and add all the column values to a 2D array, which we will return as the answer.

Solution:

Let’s look at the code for the above approach:

C++ Code:

class Solution {
public:
vector> verticalTraversal(TreeNode* root) {

``````    // Map to keep all nodes' values in their respective columns
map<int, vector<pair<int,int>>> m;

// Queue to traverse the tree level by level
queue<pair<TreeNode*,pair<int,int>>> q;

// Starting from the root node with column index 0 and row index 0
q.push(make_pair(root,make_pair(0,0)));

// Column minimum and maximum values
int colMin = INT_MAX, colMax = INT_MIN;

// Traverse until queue is empty
while(!q.empty()) {

// Get values from front of queue
auto front = q.front();
q.pop();
TreeNode* node = front.first;
int col = front.second.first;
int row = front.second.second;

// Add node to map column
m[col].push_back(make_pair(row,node->val));

// Update column minimum and maximum values
colMin = min(colMin,col);
colMax = max(colMax,col);

// Insert left child to queue
if(node->left) q.push(make_pair(node->left,make_pair(col-1,row+1)));

// Insert right child to queue
if(node->right) q.push(make_pair(node->right,make_pair(col+1,row+1)));
}

// Create result 2D array
vector<vector<int>> res;

// Iterate through columns in map
for(int i=colMin;i<=colMax;i++) {

// Get all nodes of current column
auto colNodes = m[i];

// Sort the nodes based on row and value
sort(colNodes.begin(),colNodes.end());

// Add current column nodes to result row
vector<int> rowNodes;
for(auto p:colNodes) rowNodes.push_back(p.second);

// Add current row to result 2D array
res.push_back(rowNodes);

}

return res;
}
``````

};

Time Complexity:

The time complexity of the above solution is O(nlogn), where n is the number of nodes in the tree. This is because we are iterating through the tree level by level, and sorting the nodes in each column, which takes O(logn) time. Since we do this for all n nodes, the overall time complexity is O(nlogn).

Space Complexity:

The space complexity of the above solution is O(n), where n is the number of nodes in the tree. This is because we are using a map to store all nodes in their respective columns, which could have up to n elements in the worst case. Additionally, we are using a queue to traverse the tree level by level, which could have up to n/2 elements in the worst case. Therefore, the overall space complexity is O(n).

## Step by Step Implementation For Vertical Order Traversal Of A Binary Tree

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List> verticalOrder(TreeNode root) {

// check for empty tree
if (root == null) {
return new ArrayList<>();
}

// create a map to store the vertical order traversal
Map> map = new TreeMap<>();

// create a queue for Breadth First Search

// start the BFS from the root node

// run till queue is not empty
while (!queue.isEmpty()) {

// remove the front element from the queue
TreeNode node = queue.poll();
int col = cols.poll();

// if this column is not present in the map, then create a new list
if (!map.containsKey(col)) {
map.put(col, new ArrayList<>());
}

// add the node to the map

// if the node has a left child, add it to the queue
if (node.left != null) {
}

// if the node has a right child, add it to the queue
if (node.right != null) {
}
}

// return the vertical order traversal of the tree
return new ArrayList<>(map.values());
}
}```
```from collections import defaultdict

# A utility function to create a new node
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None

# Function to Build Tree
def buildTree(string):
# Corner Case
if(string == "N"):
return None

# Creating list of strings from input
# string after spliting by space
ip = list(map(str, string.split()))

# Create the root of the tree
root = Node(int(ip))
size = 0
q = [root]

# Starting from the second element
i = 1
while(size > 0 and i < len(ip)):
# Get and remove the front of the queue
currNode = q
q.pop(0)
size = size-1

# Get the current node's value from the string
currVal = ip[i]

# If the left child is not null
if(currVal != "N"):

# Create the left child for the current node
currNode.left = Node(int(currVal))

# Push it to the queue
q.append(currNode.left)
size = size+1
# For the right child
i = i+1
if(i >= len(ip)):
break
currVal = ip[i]

# If the right child is not null
if(currVal != "N"):

# Create the right child for the current node
currNode.right = Node(int(currVal))

# Push it to the queue
q.append(currNode.right)
size = size+1
i = i+1
return root

def verticalOrder(root):
# Base case
if root is None:
return

# Create empty queues for
#  level order traversal
dict = defaultdict(list) #dictionary that stores the nodes at each horizontal distance
hd = 0 #horizontal distance of the root
queue = [] #queue for level order traversal

# Enqueue Root and initialize HD as 0
queue.append(root)

while(len(queue) > 0):
# Extract the node at the front of
#  the queue and its horizontal
# distance from the root
temp = queue.pop(0)
hd = temp.hd

# Add the extracted node to the
# dictionary dict
dict[hd].append(temp.data)

# Enqueue left and right children
if temp.left:
temp.left.hd = hd-1
queue.append(temp.left)

if temp.right:
temp.right.hd = hd+1
queue.append(temp.right)
# Traverse the dictionary and print nodes at
#  each horizontal distance (hd)
for index, value in sorted(dict.items()):
for i in value:
print(i, end=" ")
print()

if __name__ == '__main__':
t = int(input())

for i in range(t):
string = input()
root = buildTree(string)
verticalOrder(root)
print()```
```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var verticalOrder = function(root) {
if(!root) return [];

let map = {};
let queue = [[root, 0]];
let min = 0;
let max = 0;

while(queue.length) {
let [node, col] = queue.shift();
if(!map[col]) map[col] = [node.val];
else map[col].push(node.val);
min = Math.min(min, col);
max = Math.max(max, col);
if(node.left) queue.push([node.left, col - 1]);
if(node.right) queue.push([node.right, col + 1]);
}

let ans = [];
for(let i = min; i <= max; i++) {
ans.push(map[i]);
}
return ans;
};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector> verticalTraversal(TreeNode* root) {

// Base case
if (!root) {
return {};
}

// Result vector
vector> res;

// Queue for BFS
queue> q;

// Map for storing the nodes at each horizontal distance
map> m;

// Variable for tracking the minimum horizontal distance
int min_hd = 0;

// Variable for tracking the maximum horizontal distance
int max_hd = 0;

// Enqueue the root node with horizontal distance as 0
q.push({root, 0});

// Loop while queue is not empty
while (!q.empty()) {

// Get the size of the queue
int size = q.size();

// Set of values at each horizontal distance
// This is required to maintain the order of nodes at same horizontal distance
map> temp;

// Loop through all the nodes in the queue
for (int i = 0; i < size; i++) {

// Dequeue a node from the queue
auto node = q.front();
q.pop();

// Get the horizontal distance of the dequeued node
int hd = node.second;

// Get the value of the dequeued node
int val = node.first->val;

// Insert the value in the set at the horizontal distance
temp[hd].insert(val);

// Update the minimum horizontal distance
min_hd = min(min_hd, hd);

// Update the maximum horizontal distance
max_hd = max(max_hd, hd);

// If the dequeued node has a left child, enqueue it
if (node.first->left) {
q.push({node.first->left, hd - 1});
}

// If the dequeued node has a right child, enqueue it
if (node.first->right) {
q.push({node.first->right, hd + 1});
}
}

// Loop through the map to insert the nodes at each horizontal distance in the result vector
for (int i = min_hd; i <= max_hd; i++) {
res.push_back({temp[i].begin(), temp[i].end()});
}
}

return res;
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
public class Solution {
public IList> VerticalTraversal(TreeNode root) {

//Create a dictionary to store the vertical order traversal
Dictionary> dict = new Dictionary>();

//Create a queue to do a level order traversal
Queue queue = new Queue();
Queue cols = new Queue();

//Start the traversal from the root node
queue.Enqueue(root);
cols.Enqueue(0);

//Loop through the queue while it's not empty
while(queue.Count != 0){
//Get the size of the queue
int size = queue.Count;

//Create a list to store the nodes at the same horizontal distance
List list = new List();

//Loop through the queue
for(int i = 0; i < size; i++){
//Get the node at the front of the queue
TreeNode node = queue.Dequeue();

//Get the column value of the node
int col = cols.Dequeue();

//Check if the column value is in the dictionary
if(!dict.ContainsKey(col)){
//If it's not, add it to the dictionary
}

//Add the node to the list

//Check if the node has a left child
if(node.left != null){
//If it does, add it to the queue
queue.Enqueue(node.left);

//Add the column value - 1 to the queue
cols.Enqueue(col - 1);
}

//Check if the node has a right child
if(node.right != null){
//If it does, add it to the queue
queue.Enqueue(node.right);

//Add the column value + 1 to the queue
cols.Enqueue(col + 1);
}
}

//Add the list of nodes to the dictionary
}

//Create a list to store the final result
List> result = new List>();

//Loop through the dictionary
foreach(var key in dict.Keys){
//Add the list of nodes at the same horizontal distance to the final result
}

//Return the final result
return result;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]