Vertical order traversal of Binary Tree using Map

Last Updated : 19 Apr, 2023

Given a binary tree, print it vertically. The following examples illustrate the vertical order traversal.

Examples:

Input: 1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9

Output:

4
2
1 5 6
3 8
7
9

Vertical order traversal of the binary tree using Self Balancing BSTs:

To solve the problem follow the below idea:

We need to check the Horizontal Distances from the root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on the same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance.

Follow the below steps to solve the problem:

Do a preorder traversal of the given Binary Tree.
While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for the root.
For the left subtree, we pass the Horizontal Distance as the Horizontal distance of the root minus 1.
For the right subtree, we pass the Horizontal Distance as the Horizontal Distance of the root plus 1.
For every HD value, we maintain a list of nodes in a hash map. Whenever we see a node in traversal, we go to the hash map entry and add the node to the hash map using HD as a key in a map.

Below is the implementation of the above approach, thanks to Chirag for providing the below C++ implementation:

C++

// C++ program for printing vertical order of a given binary
// tree
#include <bits/stdc++.h>
using namespace std;
 
// Structure for a binary tree node
struct Node {
    int key;
    Node *left, *right;
};
 
// A utility function to create a new node
struct Node* newNode(int key)
{
    struct Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
 
// Utility function to store vertical order in map 'm'
// 'hd' is horizontal distance of current node from root.
// 'hd' is initially passed as 0
void getVerticalOrder(Node* root, int hd,
                      map<int, vector<int> >& m)
{
    // Base case
    if (root == NULL)
        return;
 
    // Store current node in map 'm'
    m[hd].push_back(root->key);
 
    // Store nodes in left subtree
    getVerticalOrder(root->left, hd - 1, m);
 
    // Store nodes in right subtree
    getVerticalOrder(root->right, hd + 1, m);
}
 
// The main function to print vertical order of a binary
// tree with the given root
void printVerticalOrder(Node* root)
{
    // Create a map and store vertical order in map using
    // function getVerticalOrder()
    map<int, vector<int> > m;
    int hd = 0;
    getVerticalOrder(root, hd, m);
 
    // Traverse the map and print nodes at every horizontal
    // distance (hd)
    map<int, vector<int> >::iterator it;
    for (it = m.begin(); it != m.end(); it++) {
        for (int i = 0; i < it->second.size(); ++i)
            cout << it->second[i] << " ";
        cout << endl;
    }
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
    root->right->right->right = newNode(9);
    cout << "Vertical order traversal is \n";
 
    // Function call
    printVerticalOrder(root);
    return 0;
}

Java

// Java program for printing vertical order of a given
// binary tree
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.Vector;
 
public class VerticalOrderBtree {
    // Tree node
    static class Node {
        int key;
        Node left;
        Node right;
 
        // Constructor
        Node(int data)
        {
            key = data;
            left = null;
            right = null;
        }
    }
 
    // Utility function to store vertical order in map 'm'
    // 'hd' is horizontal distance of current node from
    // root. 'hd' is initially passed as 0
    static void
    getVerticalOrder(Node root, int hd,
                     TreeMap<Integer, Vector<Integer> > m)
    {
        // Base case
        if (root == null)
            return;
 
        // get the vector list at 'hd'
        Vector<Integer> get = m.get(hd);
 
        // Store current node in map 'm'
        if (get == null) {
            get = new Vector<>();
            get.add(root.key);
        }
        else
            get.add(root.key);
 
        m.put(hd, get);
 
        // Store nodes in left subtree
        getVerticalOrder(root.left, hd - 1, m);
 
        // Store nodes in right subtree
        getVerticalOrder(root.right, hd + 1, m);
    }
 
    // The main function to print vertical order of a binary
    // tree with the given root
    static void printVerticalOrder(Node root)
    {
        // Create a map and store vertical order in map
        // using function getVerticalOrder()
        TreeMap<Integer, Vector<Integer> > m
            = new TreeMap<>();
        int hd = 0;
        getVerticalOrder(root, hd, m);
 
        // Traverse the map and print nodes at every
        // horizontal distance (hd)
        for (Entry<Integer, Vector<Integer> > entry :
             m.entrySet()) {
            System.out.println(entry.getValue());
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // TO DO Auto-generated method stub
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.right = new Node(8);
        root.right.right.right = new Node(9);
        System.out.println("Vertical Order traversal is");
        printVerticalOrder(root);
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python3 program for printing vertical order of a given
# binary tree
 
# A binary tree node
 
 
class Node:
    # Constructor to create a new node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# Utility function to store vertical order in map 'm'
# 'hd' is horizontal distance of current node from root
# 'hd' is initially passed as 0
 
 
def getVerticalOrder(root, hd, m):
 
    # Base Case
    if root is None:
        return
 
    # Store current node in map 'm'
    try:
        m[hd].append(root.key)
    except:
        m[hd] = [root.key]
 
    # Store nodes in left subtree
    getVerticalOrder(root.left, hd-1, m)
 
    # Store nodes in right subtree
    getVerticalOrder(root.right, hd+1, m)
 
# The main function to print vertical order of a binary
# tree ith given root
 
 
def printVerticalOrder(root):
 
    # Create a map and store vertical order in map using
    # function getVerticalORder()
    m = dict()
    hd = 0
    getVerticalOrder(root, hd, m)
 
    # Traverse the map and print nodes at every horizontal
    # distance (hd)
    for index, value in enumerate(sorted(m)):
        for i in m[value]:
            print(i, end=" ")
        print()
 
 
# Driver program to test above function
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.right.left.right = Node(8)
    root.right.right.right = Node(9)
    print("Vertical order traversal is")
    printVerticalOrder(root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program for printing vertical order of a given binary
// tree
using System;
using System.Collections.Generic;
 
public class VerticalOrderBtree {
 
    // Tree node
    public class Node {
        public int key;
        public Node left;
        public Node right;
 
        // Constructor
        public Node(int data)
        {
            key = data;
            left = null;
            right = null;
        }
    }
 
    // Utility function to store vertical order in map 'm'
    // 'hd' is horizontal distance of current node from
    // root. 'hd' is initially passed as 0
    static void
    getVerticalOrder(Node root, int hd,
                     SortedDictionary<int, List<int> > m)
    {
        // Base case
        if (root == null)
            return;
 
        // get the vector list at 'hd'
        List<int> get = new List<int>(); // m[hd];
        if (m.ContainsKey(hd))
            get.AddRange(m[hd]);
 
        // Store current node in map 'm'
        if (get == null) {
            get = new List<int>();
            get.Add(root.key);
        }
        else
            get.Add(root.key);
 
        m[hd] = get;
 
        // Store nodes in left subtree
        getVerticalOrder(root.left, hd - 1, m);
 
        // Store nodes in right subtree
        getVerticalOrder(root.right, hd + 1, m);
    }
 
    // The main function to print vertical order of a binary
    // tree with the given root
    static void printVerticalOrder(Node root)
    {
 
        // Create a map and store vertical order in map
        // using function getVerticalOrder()
        SortedDictionary<int, List<int> > m
            = new SortedDictionary<int, List<int> >();
        int hd = 0;
        getVerticalOrder(root, hd, m);
 
        // Traverse the map and print nodes at every
        // horizontal distance (hd)
        foreach(KeyValuePair<int, List<int> > entry in m)
        {
            foreach(int v in entry.Value)
                Console.Write(v + " ");
            Console.WriteLine();
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
 
        // TO DO Auto-generated method stub
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.right = new Node(8);
        root.right.right.right = new Node(9);
        Console.WriteLine("Vertical Order traversal is");
        printVerticalOrder(root);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

// javascript program for printing vertical order of a given binary
// tree
 
 
// Structure for a binary tree node
class Node {
     
    constructor(val){
        this.key = val;
        this.left = null;
        this.right = null;
    }
}
 
 
// Utility function to store vertical order in map 'm'
// 'hd' is horizontal distance of current node from root.
// 'hd' is initially passed as 0
function getVerticalOrder(root, hd, m)
{
    // Base case
    if (root == null)
        return;
 
    // Store current node in map 'm'
    if((hd in m) == false){
        m[hd] = new Array();
    }
    m[hd].push(root.key);
 
    // Store nodes in left subtree
    getVerticalOrder(root.left, hd - 1, m);
 
    // Store nodes in right subtree
    getVerticalOrder(root.right, hd + 1, m);
}
 
//  custom sort function. 
function sortFunction(a, b) {
    if (a[0] === b[0]) {
        return 0;
    }
    else {
        return (a[0] < b[0]) ? -1 : 1;
    }
}
 
// The main function to print vertical order of a binary
// tree with the given root
function printVerticalOrder(root)
{
    // Create a map and store vertical order in map using
    // function getVerticalOrder()
    let m = {};
    let hd = 0;
    getVerticalOrder(root, hd, m);
 
    // Traverse the map and print nodes at every horizontal
    // distance (hd)
    // store the map in the array, as keys act as characters, and cannot be sorted numerically. 
    let x = new Array();
     
    for (const key in m) {
        let y = new Array();
        y.push(parseInt(key));
        for(let i = 0; i < m[key].length; i++){
            y.push(m[key][i]);
        }
        x.push(y);
    }
     
    // sort in ascending order. 
    x.sort(sortFunction);
     
    // print then. 
    for(let i = 0; i < x.length; i++){
        for(let j = 0; j < x[i].length; j++){
            if(j == 0) continue;
             
            document.write(x[i][j] + " ");
        }
        document.write("\n");
    }
     
}
 
// Driver code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.right = new Node(8);
root.right.right.right = new Node(9);
console.log("Vertical order traversal is \n");
 
// Function call
printVerticalOrder(root);
 
// The code is contributed by Nidhi goel.

Output

Vertical order traversal is 
4 
2 
1 5 6 
3 8 
7 
9

Time Complexity: O(N log N). The hashing based solution can be considered as O(N) under the assumption that we have a good hashing function that allows insertion and retrieval operations in O(1) time. In the above C++ implementation, map of STL is used. map in STL is typically implemented using a Self-Balancing Binary Search Tree where all operations take O(Log N) time.
Auxiliary Space: O(N)

Note: The above solution may not print nodes in the same vertical order as they appear in the tree.
For example, the above program prints 12 before 9. See this for a sample run.

1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
/ \
10 11
\
12

Refer below post for a level order traversal-based solution. The below post makes sure that nodes of a vertical line are printed in the same order as they appear in the tree: Print a Binary Tree in Vertical Order | Set 3 (Using Level Order Traversal)

Print vertical order traversal of the binary tree in the same order as they appear:

To solve the problem follow the below idea:

We can also maintain the order of nodes in the same vertical order as they appear in the tree. Nodes having the same horizontal distance will print according to level order.
For example, In below diagram 9 and 12 have the same horizontal distance. We can make sure that if a node like 12 comes below in the same vertical line, it is printed after a node like 9

Idea: Instead of using horizontal distance as a key in the map, we will use horizontal distance + vertical distance as the key. We know that the number of nodes can’t be more than the integer range in a binary tree.
We will use the first 30 bits of the key for horizontal distance [MSB to LSB] and will use the 30 next bits for vertical distance. Thus keys will be stored in the map as per our requirement.

Follow the below steps to solve the problem:

Declare a map to store the value of nodes at each level
If the root is null then return from the function(Base case)
Create an integer val and set its value to horizontal distance << 30 OR vertical distance
Push root->data in the map using val as the key
Recur for root->left and root->right with horizontal distance – 1, vertical distance + 1 and horizontal distance + 1, vertical distance -1 respectively
Print the solution using map

Below is the implementation of the above approach:

C++14

// C++ program for printing
// vertical order of a given binary
// tree
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int data;
    Node *left, *right;
};
 
struct Node* newNode(int data)
{
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// Store vertical order
// in map "m", hd = horizontal
// distance, vd = vertical distance
void preOrderTraversal(Node* root, long long int hd,
                       long long int vd,
                       map<long long int, vector<int> >& m)
{
    if (!root)
        return;
    // key = horizontal
    // distance (30 bits) + vertical
    // distance (30 bits) map
    // will store key in sorted
    // order. Thus nodes having same
    // horizontal distance
    // will sort according to
    // vertical distance.
    long long val = hd << 30 | vd;
 
    // insert in map
    m[val].push_back(root->data);
 
    preOrderTraversal(root->left, hd - 1, vd + 1, m);
    preOrderTraversal(root->right, hd + 1, vd + 1, m);
}
 
void verticalOrder(Node* root)
{
    // map to store all nodes in vertical order.
    // keys will be horizontal + vertical distance.
    map<long long int, vector<int> > mp;
 
    preOrderTraversal(root, 0, 1, mp);
 
    // print map
    int prekey = INT_MAX;
    map<long long int, vector<int> >::iterator it;
    for (it = mp.begin(); it != mp.end(); it++) {
        if (prekey != INT_MAX
            && (it->first >> 30) != prekey) {
            cout << endl;
        }
        prekey = it->first >> 30;
        for (int j = 0; j < it->second.size(); j++)
            cout << it->second[j] << " ";
    }
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
    root->right->right->right = newNode(9);
    cout << "Vertical order traversal :- " << endl;
    verticalOrder(root);
    return 0;
}

Java

// Java program for printing vertical order of a given
// binary tree
 
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.Vector;
 
public class VerticalOrderBtree {
    // Tree node
    static class Node {
        int data;
        Node left;
        Node right;
 
        // Constructor
        Node(int key)
        {
            data = key;
            left = null;
            right = null;
        }
    }
    // Store vertical order
    // in map "m", hd = horizontal
    // distance, vd = vertical distance
    static void
    preOrderTraversal(Node root, long hd, long vd,
                      TreeMap<Long, Vector<Integer> > m)
    {
        if (root == null)
            return;
        // key = horizontal
        // distance (30 bits) + vertical
        // distance (30 bits) map
        // will store key in sorted
        // order. Thus nodes having same
        // horizontal distance
        // will sort according to
        // vertical distance.
        long val = hd << 30 | vd;
 
        // insert in map
        if (m.get(val) != null)
            m.get(val).add(root.data);
        else {
            Vector<Integer> v = new Vector<Integer>();
            v.add(root.data);
            m.put(val, v);
        }
        preOrderTraversal(root.left, hd - 1, vd + 1, m);
        preOrderTraversal(root.right, hd + 1, vd + 1, m);
    }
 
    static void verticalOrder(Node root)
    {
        // map to store all nodes in vertical order.
        // keys will be horizontal + vertical distance.
        TreeMap<Long, Vector<Integer> > mp
            = new TreeMap<>();
 
        preOrderTraversal(root, 0, 1, mp);
 
        // print map
        int prekey = Integer.MAX_VALUE;
        for (Entry<Long, Vector<Integer> > entry :
             mp.entrySet()) {
            if (prekey != Integer.MAX_VALUE
                && (entry.getKey() >> 30) != prekey) {
                System.out.println();
            }
            prekey = (int)(entry.getKey() >> 30);
            for (int x : entry.getValue())
                System.out.print(x + " ");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.right = new Node(8);
        root.right.right.right = new Node(9);
        System.out.println("Vertical Order traversal :- ");
        verticalOrder(root);
    }
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Python3

import sys
 
# Python program for printing
# vertical order of a given binary
# tree
 
 
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Store vertical order
# in map "m", hd = horizontal
# distance, vd = vertical distance
 
 
def preOrderTraversal(root, hd, vd, m):
    if not root:
        return
    # key = horizontal
    # distance (30 bits) + vertical
    # distance (30 bits) map
    # will store key in sorted
    # order. Thus nodes having same
    # horizontal distance
    # will sort according to
    # vertical distance.
    val = hd << 30 | vd
 
    # insert in map
    if val in m:
        m[val].append(root.data)
    else:
        m[val] = [root.data]
    preOrderTraversal(root.left, hd-1, vd+1, m)
    preOrderTraversal(root.right, hd+1, vd+1, m)
 
 
def verticalOrder(root):
 
    mp = dict()
 
    preOrderTraversal(root, 0, 0, mp)
 
    # print dictionary
    prekey = sys.maxsize
 
    for i in sorted(mp.keys()):
        if (prekey != sys.maxsize) and (i >> 30 != prekey):
            print()
        prekey = i >> 30
        for j in mp[i]:
            print(j, end=" ")
 
 
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)
print("Vertical order traversal :- ")
verticalOrder(root)
 
# This code is contributed by prashantchandelme.

C#

// C# program for printing vertical order of a given binary
// tree
using System;
using System.Collections.Generic;
 
public class VerticalOrderBtree {
 
    // Tree node
    public class Node {
        public int data;
        public Node left;
        public Node right;
 
        // Constructor
        public Node(int val)
        {
            data = val;
            left = null;
            right = null;
        }
    }
    // Store vertical order
    // in map "m", hd = horizontal
    // distance, vd = vertical distance
    static void
    preOrderTraversal(Node root, long hd, long vd,
                      SortedDictionary<long, List<int> > m)
    {
        if (root == null)
            return;
        // key = horizontal
        // distance (30 bits) + vertical
        // distance (30 bits) map
        // will store key in sorted
        // order. Thus nodes having same
        // horizontal distance
        // will sort according to
        // vertical distance.
        long val = hd << 30 | vd;
 
        // insert in map
        if (m.ContainsKey(val) == true)
            m[val].Add(root.data);
        else {
            List<int> v = new List<int>();
            v.Add(root.data);
            m.Add(val, v);
        }
        preOrderTraversal(root.left, hd - 1, vd + 1, m);
        preOrderTraversal(root.right, hd + 1, vd + 1, m);
    }
 
    static void verticalOrder(Node root)
    {
        // map to store all nodes in vertical order.
        // keys will be horizontal + vertical distance.
        SortedDictionary<long, List<int> > mp
            = new SortedDictionary<long, List<int> >();
 
        preOrderTraversal(root, 0, 1, mp);
 
        // print map
        int prekey = Int32.MaxValue;
        foreach(KeyValuePair<long, List<int> > entry in mp)
        {
            if (prekey != Int32.MaxValue
                && (entry.Key >> 30) != prekey) {
                Console.WriteLine();
            }
            prekey = (int)entry.Key >> 30;
            foreach(int v in entry.Value)
                Console.Write(v + " ");
        }
    }
 
    // Driver program to test above functions
    public static void Main(String[] args)
    {
 
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.right = new Node(8);
        root.right.right.right = new Node(9);
        Console.WriteLine("Vertical Order traversal :- ");
        verticalOrder(root);
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Javascript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
 
function preOrderTraversal(root, hd, vd, m) {
  if (!root) return;
 
  // key = horizontal distance (30 bits) + vertical distance (30 bits)
  // map will store key in sorted order. Thus nodes having same
  // horizontal distance will sort according to vertical distance.
  const val = BigInt(hd << 30n | vd);
 
  // insert in map
  if (!m.has(val)) {
    m.set(val, []);
  }
  m.get(val).push(root.data);
 
  preOrderTraversal(root.left, hd - 1n, vd + 1n, m);
  preOrderTraversal(root.right, hd + 1n, vd + 1n, m);
}
 
function verticalOrder(root) {
  // map to store all nodes in vertical order.
  // keys will be horizontal + vertical distance.
  const mp = new Map();
 
  preOrderTraversal(root, 0n, 1n, mp);
 
  // print map
  let prekey = BigInt(Number.MAX_SAFE_INTEGER);
  for (const [key, value] of [...mp.entries()].sort((a, b) => {
    // sort map entries by key
    if (a[0] < b[0]) return -1;
    if (a[0] > b[0]) return 1;
    return 0;
  })) {
    if (prekey !== (key >> 30n)) {
      console.log();
    }
    prekey = key >> 30n;
    process.stdout.write(value.join(" ") + " ");
  }
}
 
// Driver code
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.right = new Node(8);
root.right.right.right = new Node(9);
 
process.stdout.write("Vertical order traversal :- ");
verticalOrder(root);

Output

Vertical order traversal :- 
4 
2 
1 5 6 
3 8 
7 
9

Time Complexity: O(N Log N)
Auxiliary Space: O(N)

Vertical order traversal of the binary tree using computeIfAbsent method in Java:

We can write the code in a more concise way, by using computeIfAbsent method of the map in java and by using a treemap for natural sorting based upon keys.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// structure of the tree node
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int item)
    {
        data = item;
        left = right = NULL;
    }
};
 
class BinaryTree {
public:
    Node* root;
 
    // Values class
    class Values {
    public:
        int max, min;
    };
 
    // Program to find vertical Order
    void verticalOrder(Node* node)
    {
        Values val;
 
        // Create TreeMap
        map<int, vector<int> > mp;
 
        // Function Call to findHorizontalDistance
        findHorizontalDistance(node, &val, &val, 0, mp);
 
        // Iterate over map.values()
        for (auto list : mp) {
            for (auto element : list.second) {
                cout << element << " ";
            }
            cout << endl;
        }
    }
 
    // Program to find Horizontal Distance
    void findHorizontalDistance(Node* node, Values* min,
                                Values* max, int hd,
                                map<int, vector<int> >& mp)
    {
        // If node is null
        if (node == NULL)
            return;
 
        // if hd is less than min.min
        if (hd < min->min)
            min->min = hd;
 
        // if hd is greater than min.min
        if (hd > max->max)
            max->max = hd;
 
        // Using computeIfAbsent
        mp[hd].push_back(node->data);
 
        // Function Call with hd equal to hd - 1
        findHorizontalDistance(node->left, min, max, hd - 1,
                               mp);
 
        // Function Call with hd equal to hd + 1
        findHorizontalDistance(node->right, min, max,
                               hd + 1, mp);
    }
};
 
int main()
{
    BinaryTree tree;
 
    // Let us construct the tree shown in above diagram
    tree.root = new Node(1);
    tree.root->left = new Node(2);
    tree.root->right = new Node(3);
    tree.root->left->left = new Node(4);
    tree.root->left->right = new Node(5);
    tree.root->right->left = new Node(6);
    tree.root->right->right = new Node(7);
    tree.root->right->left->right = new Node(8);
    tree.root->right->right->right = new Node(9);
 
    cout << "vertical order traversal is :\n";
 
    // Function Call
    tree.verticalOrder(tree.root);
    return 0;
}

Java

// Java Program for above approach
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
 
class Node {
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
 
    Node root;
 
    // Values class
    class Values {
        int max, min;
    }
 
    // Program to find vertical Order
    public void verticalOrder(Node node)
    {
        Values val = new Values();
 
        // Create TreeMap
        Map<Integer, List<Integer> > map
            = new TreeMap<Integer, List<Integer> >();
 
        // Function Call to findHorizontalDistance
        findHorizontalDistance(node, val, val, 0, map);
 
        // Iterate over map.values()
        for (List<Integer> list : map.values()) {
            System.out.println(list);
        }
    }
 
    // Program to find Horizontal Distance
    public void
    findHorizontalDistance(Node node, Values min,
                           Values max, int hd,
                           Map<Integer, List<Integer> > map)
    {
 
        // If node is null
        if (node == null)
            return;
 
        // if hd is less than min.min
        if (hd < min.min)
            min.min = hd;
 
        // if hd is greater than min.min
        if (hd > max.max)
            max.max = hd;
 
        // Using computeIfAbsent
        map.computeIfAbsent(hd,
                            k -> new ArrayList<Integer>())
            .add(node.data);
 
        // Function Call with hd equal to hd - 1
        findHorizontalDistance(node.left, min, max, hd - 1,
                               map);
 
        // Function Call with hd equal to hd + 1
        findHorizontalDistance(node.right, min, max, hd + 1,
                               map);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        BinaryTree tree = new BinaryTree();
 
        /* Let us construct the tree shown
                             in above diagram */
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.right = new Node(8);
        tree.root.right.right.right = new Node(9);
 
        System.out.println("vertical order traversal is :");
 
        // Function Call
        tree.verticalOrder(tree.root);
    }
}

C#

// C# Program for above approach
using System;
using System.Collections.Generic;
 
public class Node {
    public int data;
    public Node left, right;
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
 
    public Node root;
 
    // Values class
    public class Values {
        public int max, min;
    }
 
    // Program to find vertical Order
    public void verticalOrder(Node node)
    {
        Values val = new Values();
 
        // Create TreeMap
        SortedDictionary<int, List<int> > map
            = new SortedDictionary<int, List<int> >();
 
        // Function Call to findHorizontalDistance
        findHorizontalDistance(node, val, val, 0, map);
 
        // Iterate over map.values()
        foreach(List<int> list in map.Values)
        {
            Console.WriteLine(String.Join(" ", list));
        }
    }
 
    // Program to find Horizontal Distance
    public static void findHorizontalDistance(
        Node node, Values min, Values max, int hd,
        SortedDictionary<int, List<int> > map)
    {
 
        // If node is null
        if (node == null)
            return;
 
        // if hd is less than min.min
        if (hd < min.min)
            min.min = hd;
 
        // if hd is greater than min.min
        if (hd > max.max)
            max.max = hd;
 
        // Using TryGetValue and Add methods
        if (!map.TryGetValue(hd, out List<int> value)) {
            value = new List<int>();
            map.Add(hd, value);
        }
        value.Add(node.data);
 
        // Function Call with hd equal to hd - 1
        findHorizontalDistance(node.left, min, max, hd - 1,
                               map);
 
        // Function Call with hd equal to hd + 1
        findHorizontalDistance(node.right, min, max, hd + 1,
                               map);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
 
        BinaryTree tree = new BinaryTree();
 
        /* Let us construct the tree shown
                             in above diagram */
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.right = new Node(8);
        tree.root.right.right.right = new Node(9);
 
        Console.WriteLine("vertical order traversal is :");
 
        // Function Call
        tree.verticalOrder(tree.root);
    }
}
 
// The code is contributed by Arushi Goel.

Python3

class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
 
 
class BinaryTree:
    def __init__(self):
        self.root = None
 
    class Values:
        def __init__(self):
            self.max = float('-inf')
            self.min = float('inf')
 
    def verticalOrder(self, node):
        val = self.Values()
 
        # Create dictionary to store vertical order
        mp = {}
 
        # Function call to findHorizontalDistance
        self.findHorizontalDistance(node, val, val, 0, mp)
 
        # Iterate over dictionary values
        for hd, lst in sorted(mp.items()):
            for element in lst:
                print(element, end=" ")
            print()
 
    def findHorizontalDistance(self, node, minVal, maxVal, hd, mp):
        # If node is None
        if node is None:
            return
 
        # if hd is less than min.min
        if hd < minVal.min:
            minVal.min = hd
 
        # if hd is greater than min.min
        if hd > maxVal.max:
            maxVal.max = hd
 
        # Using setdefault
        mp.setdefault(hd, []).append(node.data)
 
        # Function Call with hd equal to hd - 1
        self.findHorizontalDistance(node.left, minVal, maxVal, hd - 1, mp)
 
        # Function Call with hd equal to hd + 1
        self.findHorizontalDistance(node.right, minVal, maxVal, hd + 1, mp)
 
 
if __name__ == '__main__':
    tree = BinaryTree()
 
    # Let us construct the tree shown in above diagram
    tree.root = Node(1)
    tree.root.left = Node(2)
    tree.root.right = Node(3)
    tree.root.left.left = Node(4)
    tree.root.left.right = Node(5)
    tree.root.right.left = Node(6)
    tree.root.right.right = Node(7)
    tree.root.right.left.right = Node(8)
    tree.root.right.right.right = Node(9)
 
    print("Vertical order traversal is:\n")
 
    # Function Call
    tree.verticalOrder(tree.root)

Javascript

// Javascript code addition 
 
class Node {
  constructor(item) {
    this.data = item;
    this.left = null;
    this.right = null;
  }
}
 
class BinaryTree {
  constructor() {
    this.root = null;
  }
 
  verticalOrder(node) {
    let val = new Values();
 
    // Create dictionary to store vertical order
    let mp = {};
 
    // Function call to findHorizontalDistance
    this.findHorizontalDistance(node, val, val, 0, mp);
 
    // Iterate over dictionary values
    for (let hd of Object.keys(mp).sort((a, b) => a - b)) {
      let lst = mp[hd];
      for (let element of lst) {
        process.stdout.write(element + " ");
      }
      process.stdout.write("\n");
    }
  }
 
  findHorizontalDistance(node, minVal, maxVal, hd, mp) {
    // If node is null
    if (!node) {
      return;
    }
 
    // if hd is less than min.min
    if (hd < minVal.min) {
      minVal.min = hd;
    }
 
    // if hd is greater than min.min
    if (hd > maxVal.max) {
      maxVal.max = hd;
    }
 
    // Using setdefault
    if (!mp[hd]) {
      mp[hd] = [];
    }
    mp[hd].push(node.data);
 
    // Function Call with hd equal to hd - 1
    this.findHorizontalDistance(node.left, minVal, maxVal, hd - 1, mp);
 
    // Function Call with hd equal to hd + 1
    this.findHorizontalDistance(node.right, minVal, maxVal, hd + 1, mp);
  }
}
 
class Values {
  constructor() {
    this.max = -Infinity;
    this.min = Infinity;
  }
}
 
let tree = new BinaryTree();
 
// Let us construct the tree shown in above diagram
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.right.left.right = new Node(8);
tree.root.right.right.right = new Node(9);
 
process.stdout.write("Vertical order traversal is:\n");
 
// Function Call
tree.verticalOrder(tree.root);
 
// The code is contributed by Arushi Goel.

Output

vertical order traversal is :
[4]
[2]
[1, 5, 6]
[3, 8]
[7]
[9]

Time Complexity: O(N Log N)
Auxiliary Space: O(N)

Vertical order traversal of the binary tree using the Unordered Map method:

Note: We have seen the ordered map above but, its complexity is O(N log N), and also it does not print the vertical nodes of the same horizontal distance in the correct order.

Here we implement this using an unordered map, as the unordered map is implemented using a hash table its complexity is O(n), better than using an ordered map which is implemented using a BST.

Follow the below steps to solve the problem:

Create a queue of pair to store the node and its horizontal distance in the tree
Create a map to store the value of nodes at each horizontal distance
Now perform a BFS on the tree
At each iteration store the nodes with a particular horizontal distance in the map
Push the left and the right child of the tree with horizontal distance – 1 and horizontal distance + 1 into the queue
Print the answer using map

Note: Here for printing all nodes of the same horizontal distance from the root we use mn and mx two variables that store the minimum and maximum horizontal distance from the root:

C++

// C++ program for printing vertical
// order of a given binary tree using BFS
#include <bits/stdc++.h>
 
using namespace std;
 
// Structure for a binary tree node
struct Node {
    int key;
    Node *left, *right;
};
 
// A function to create a new node
Node* newNode(int key)
{
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
 
// The main function to print vertical
// order of a binary tree with given root
void printVerticalOrder(Node* root)
{
    // Base case
    if (!root)
        return;
 
    // Create a map and store vertical
    // order in map using
    // function getVerticalOrder()
    unordered_map<int, vector<int> > m;
    int hd = 0;
 
    // Create queue to do level order
    // traversal Every item of queue contains
    // node and horizontal distance
    queue<pair<Node*, int> > q;
    q.push({ root, hd });
 
    // mn and mx contain the minimum and
    // maximum horizontal distance from root
    int mn = 0, mx = 0;
    while (q.size() > 0) {
 
        // pop from queue front
        pair<Node*, int> temp = q.front();
        q.pop();
        hd = temp.second;
        Node* node = temp.first;
 
        // insert this node's data
        // in vector of hash
        m[hd].push_back(node->key);
 
        if (node->left)
            q.push({ node->left, hd - 1 });
        if (node->right)
            q.push({ node->right, hd + 1 });
 
        // Update mn and mx
        if (mn > hd)
            mn = hd;
        else if (mx < hd)
            mx = hd;
    }
 
    // run the loop from minimum to maximum
    // every horizontal distance hd
    for (int i = mn; i <= mx; i++) {
        vector<int> tmp = m[i];
        for (int j = 0; j < tmp.size(); j++)
            cout << tmp[j] << " ";
        cout << endl;
    }
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
    root->right->right->right = newNode(9);
    cout << "Vertical order traversal is \n";
    printVerticalOrder(root);
    return 0;
}

Java

// Java program for printing vertical
// order of a given binary tree using BFS
import java.io.*;
import java.util.*;
 
class GFG {
    // Structure for a binary tree node
    static class Node {
        int key;
        Node left, right;
        Node(int key)
        {
            this.key = key;
            left = null;
            right = null;
        }
    }
 
    static class pair {
        Node first;
        int second;
        pair(Node first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // The main function to print vertical
    // order of a binary tree with given root
    static void printVerticalOrder(Node root)
    {
        // Base case
        if (root == null)
            return;
 
        // Create a map and store vertical
        // order in map using
        // function getVerticalOrder()
        HashMap<Integer, ArrayList<Integer> > m
            = new HashMap<>();
        int hd = 0;
 
        // Create queue to do level order
        // traversal Every item of queue contains
        // node and horizontal distance
        Queue<pair> q = new ArrayDeque<>();
        q.add(new pair(root, hd));
 
        // mn and mx contain the minimum and
        // maximum horizontal distance from root
        int mn = 0, mx = 0;
        while (q.size() > 0) {
 
            // pop from queue front
            pair temp = q.remove();
 
            hd = temp.second;
            Node node = temp.first;
 
            // insert this node's data
            // in vector of hash
            if (!m.containsKey(hd))
                m.put(hd, new ArrayList<>());
            m.get(hd).add(node.key);
 
            if (node.left != null)
                q.add(new pair(node.left, hd - 1));
            if (node.right != null)
                q.add(new pair(node.right, hd + 1));
 
            // Update mn and mx
            if (mn > hd)
                mn = hd;
            else if (mx < hd)
                mx = hd;
        }
 
        // run the loop from minimum to maximum
        // every horizontal distance hd
        for (int i = mn; i <= mx; i++) {
            ArrayList<Integer> tmp = m.get(i);
            for (int j = 0; j < tmp.size(); j++)
                System.out.print(tmp.get(j) + " ");
 
            System.out.println();
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.right = new Node(8);
        root.right.right.right = new Node(9);
        System.out.println("Vertical order traversal is ");
        printVerticalOrder(root);
    }
}
 
// This code is contributed by karandeep1234

C#

// C# program for printing vertical
// order of a given binary tree using BFS
 
using System;
using System.Collections.Generic;
 
 
// Driver code
class GFG
{
 
  // Structure for a binary tree node
  class Node
  {
    public int key;
    public Node left, right;
    public Node (int key)
    {
      this.key = key;
      left = null;
      right = null;
    }
  }
 
  class pair
  {
    public Node first;
    public int second;
    public pair (Node first, int second)
    {
      this.first = first;
      this.second = second;
    }
  }
 
  // The main function to print vertical
  // order of a binary tree with given root
  static void printVerticalOrder (Node root)
  {
    // Base case
    if (root == null)
      return;
 
    // Create a map and store vertical
    // order in map using
    // function getVerticalOrder()
    Dictionary < int, List < int >>m = new Dictionary < int, List < int >>();
    int hd = 0;
 
    // Create queue to do level order
    // traversal Every item of queue contains
    // node and horizontal distance
    Queue < pair > q = new Queue < pair > ();
    q.Enqueue (new pair (root, hd));
 
    // mn and mx contain the minimum and
    // maximum horizontal distance from root
    int mn = 0, mx = 0;
    while (q.Count > 0)
      {
 
    // pop from queue front
    pair temp = q.Dequeue ();
 
    hd = temp.second;
    Node node = temp.first;
 
    // insert this node's data
    // in vector of hash
    if (!m.ContainsKey (hd))
      m.Add (hd, new List < int >());
    m[hd].Add (node.key);
 
    if (node.left != null)
      q.Enqueue (new pair (node.left, hd - 1));
    if (node.right != null)
      q.Enqueue (new pair (node.right, hd + 1));
 
    // Update mn and mx
    if (mn > hd)
      mn = hd;
    else if (mx < hd)
      mx = hd;
      }
 
    // run the loop from minimum to maximum
    // every horizontal distance hd
    for (int i = mn; i <= mx; i++)
      {
    List < int >tmp = m[i];
    for (int j = 0; j < tmp.Count; j++)
      Console.Write (tmp[j] + " ");
 
    Console.WriteLine ();
      }
  }
 
 
  static void Main ()
  {
    Node root = new Node (1);
    root.left = new Node (2);
    root.right = new Node (3);
    root.left.left = new Node (4);
    root.left.right = new Node (5);
    root.right.left = new Node (6);
    root.right.right = new Node (7);
    root.right.left.right = new Node (8);
    root.right.right.right = new Node (9);
    Console.WriteLine ("Vertical order traversal is ");
    printVerticalOrder (root);
  }
}

Javascript

// Javascript program for printing vertical
// order of a given binary tree using BFS
 
      // program to implement queue data structure
      class Queue {
        constructor() {
          this.items = Array.from(Array(), () => new Array());
        }
 
        // add element to the queue
        push(element) {
          return this.items.push(element);
        }
 
        // remove element from the queue
        pop() {
          if (this.items.length > 0) {
            return this.items.shift();
          }
        }
 
        // view the first element
        front() {
          return this.items[0];
        }
 
        // check if the queue is empty
        empty() {
          return this.items.length == 0;
        }
 
        // the size of the queue
        size() {
          return this.items.length;
        }
      }
 
      // Structure for a binary tree node
      class Node {
        constructor(key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }
      }
 
      // The main function to print vertical
      // order of a binary tree with given root
      function printVerticalOrder(root) {
        // Base case
        if (!root) return;
 
        // Create a map and store vertical
        // order in map using
        // function getVerticalOrder()
        let m = new Map();
        let hd = 0;
 
        // Create queue to do level order
        // traversal Every item of queue contains
        // node and horizontal distance
        let q = new Queue();
        q.push([root, hd]);
 
        // mn and mx contain the minimum and
        // maximum horizontal distance from root
        let mn = 0,
          mx = 0;
        while (q.size() > 0) {
          // pop from queue front
          temp = q.front();
          q.pop();
          hd = temp[1];
          node = temp[0];
 
          //insert this node's data
          //in string of hash
          if (m.get(hd) === undefined) {
            m.set(hd, "" + node.key);
          } else {
            m.set(hd, m.get(hd) + " " + node.key);
          }
 
          if (node.left) q.push([node.left, hd - 1]);
          if (node.right) q.push([node.right, hd + 1]);
 
          // Update mn and mx
          if (mn > hd) mn = hd;
          else if (mx < hd) mx = hd;
        }
 
        // run the loop from minimum to maximum
        // every horizontal distance hd
        for (let i = mn; i <= mx; i++) {
          tmp = m.get(i);
          console.log(tmp);
        }
      }
 
      // Driver code
 
      let root = new Node(1);
      root.left = new Node(2);
      root.right = new Node(3);
      root.left.left = new Node(4);
      root.left.right = new Node(5);
      root.right.left = new Node(6);
      root.right.right = new Node(7);
      root.right.left.right = new Node(8);
      root.right.right.right = new Node(9);
      console.log("Vertical order traversal is ");
      printVerticalOrder(root);

Python3

# Python program for printing vertical order of a given binary tree using BFS
 
# Structure for a binary tree node
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# A function to create a new node
def newNode(key):
    node = Node(key)
    return node
 
# The main function to print vertical
# order of a binary tree with given root
def printVerticalOrder(root):
    # Base case
    if not root:
        return
 
    # Create a dictionary and store vertical
    # order in dictionary using
    # function getVerticalOrder()
    m = {}
    hd = 0
 
    # Create queue to do level order
    # traversal Every item of queue contains
    # node and horizontal distance
    q = []
    q.append((root, hd))
 
    # mn and mx contain the minimum and
    # maximum horizontal distance from root
    mn, mx = 0, 0
    while q:
        # pop from queue front
        temp = q.pop(0)
        hd = temp[1]
        node = temp[0]
 
        # insert this node's data
        # in vector of hash
        if hd in m:
            m[hd].append(node.key)
        else:
            m[hd] = [node.key]
 
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
 
        # Update mn and mx
        if mn > hd:
            mn = hd
        elif mx < hd:
            mx = hd
 
    # run the loop from minimum to maximum
    # every horizontal distance hd
    for i in range(mn, mx+1):
        if i in m:
            tmp = m[i]
            for j in range(len(tmp)):
                print(tmp[j], end=' ')
            print()
 
# Driver code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    root.right.left = newNode(6)
    root.right.right = newNode(7)
    root.right.left.right = newNode(8)
    root.right.right.right = newNode(9)
    print("Vertical order traversal is")
    printVerticalOrder(root)

Output

Vertical order traversal is 
4 
2 
1 5 6 
3 8 
7 
9

Queue implementation in different languages

Some question related to Queue implementation

Easy problems on Queue

Intermediate problems on Queue

Hard problems on Queue

Queue implementation in different languages

Some question related to Queue implementation

Easy problems on Queue

Intermediate problems on Queue

Hard problems on Queue

Vertical order traversal of Binary Tree using Map

Vertical order traversal of the binary tree using Self Balancing BSTs:

C++

Java

Python3

C#

Javascript

Print vertical order traversal of the binary tree in the same order as they appear:

C++14

Java

Python3

C#

Javascript

Vertical order traversal of the binary tree using computeIfAbsent method in Java:

C++

Java

C#

Python3

Javascript

Vertical order traversal of the binary tree using the Unordered Map method:

C++

Java

C#

Javascript

Python3

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?