Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.
For each node at position (x, y), its left and right children will be at positions (x - 1, y - 1) and (x + 1, y - 1) respectively.
The vertical order traversal of a binary tree is a list of non-empty reports for each unique x-coordinate from left to right. Each report is a list of all nodes at a given x-coordinate. The report should be primarily sorted by y-coordinate from highest y-coordinate to lowest. If any two nodes have the same y-coordinate in the report, the node with the smaller value should appear earlier.

Find the vertical order traversal of the binary tree.

Example 1:

Input: root ={3,9,20,null,null,15,7}
Output: [[9],[3,15],[20],[7]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class VerticalOrderTraversalBT {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        List<List<Integer>> arr = verticalTraversal(root);
        System.out.println(Arrays.asList(arr));
    }

    static public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        // base condition
        if (root == null)
            return result;

        // create map
        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
        // add all value in map
        vtUtil(root, 0, 0, map);

        for (Map.Entry<Integer, TreeMap<Integer, PriorityQueue<Integer>>> entry : map.entrySet()) {
            List<Integer> line = new ArrayList<>();
            for (PriorityQueue<Integer> pq : entry.getValue().values()) {
                while (pq.size() > 0)
                    line.add(pq.poll());
            }
            result.add(line);
        }

        return result;
    }

    private static void vtUtil(TreeNode root, int x, int y,
            TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map) {
        // base condition
        if (root == null)
            return;

        TreeMap<Integer, PriorityQueue<Integer>> m = new TreeMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        if (map.containsKey(x)) {
            m = map.get(x);
            if (m.containsKey(y)) {
                pq = m.get(y);
            }
        }
        // add value
        pq.add(root.val);
        m.put(y, pq);
        map.put(x, m);

        // again call for left node
        vtUtil(root.left, x - 1, y + 1, map);
        // call for right node
        vtUtil(root.right, x + 1, y + 1, map);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
}; 



map<int,vector<pair<int,int>>> mp;
void verticalTraversal(TreeNode *root,int x,int y)
{
    if(root==NULL)
               return;
     mp[x].push_back({y,root->data});

     //call for left subtree
     verticalTraversal(root->left,x-1,y+1);

     //call for right subtree
     verticalTraversal(root->right,x+1,y+1);
}
vector<vector<int>> verticalTraversal(TreeNode* root) 
{
    verticalTraversal(root,0,0);
    vector<vector<int>> res;
     for(auto  m:mp)
     {
         sort(m.second.begin(),m.second.end());
         vector<int>v;
         for(auto x:m.second)
               v.push_back(x.second);
        res.push_back(v);
     }
       return res;
        
}

int main()
{
  TreeNode *root=new TreeNode(3);
  root->left=new TreeNode(9);
  root->right=new TreeNode(20);
  root->right->left=new TreeNode(15);
  root->right->right=new TreeNode(7);

  vector<vector<int>> arr=verticalTraversal(root);
  cout<<"[";
  for(int i=0;i<arr.size();i++)
    {
        cout<<"[";
        for(int j=0;j<arr[i].size();j++)
          {
              cout<<arr[i][j];
              if(j!=arr[i].size()-1)
                cout<<",";

          }
        cout<<"]";
        if(i!=arr.size()-1)
          cout<<",";
    }
  cout<<"]";
  return 0;
}