987. Vertical Order Traversal of a Binary Tree (Hard)

🔸 Introduction

Talk briefly about tree traversal problems and how vertical traversal adds a twist. Mention that this is a Hard-level problem and requires careful ordering based on multiple dimensions — horizontal level, depth, and node values.

Problem Summary

Explain the problem in your own words:

• Given a binary tree, return its vertical order traversal.

• When two nodes have the same vertical and depth, the node with the smaller value comes first.

• Output: List of lists, grouped by vertical column from left to right.

Question :

examples 1 :

example 2

🔸 First Attempt ( Wrong Approach)

I used a pair (level, value) to group nodes by vertical level.

Then sorted the list and built the result.

❌ Why It’s Wrong:

• It doesn’t handle depth (vertical level from top to bottom).

• So, when nodes have the same horizontal level, they get sorted only by value or insertion order, leading to wrong results.

class Solution {
public:
     void view(TreeNode* root,int level,vector<pair<int,int>>&d){
        if(root==NULL)return;

        d.push_back({level,root->val});

        view(root->left,level-1,d);
        view(root->right,level+1,d);
     }
    vector<vector<int>> verticalTraversal(TreeNode* root) {

          vector<pair<int,int>> d;
          view(root,0,d);

          if (d.empty()) return {};

          sort(d.begin(),d.end());

          int minLevel = d.front().first;
          int maxLevel = d.back().first;
          int size = maxLevel - minLevel + 1;
          vector<vector<int>> res(size);
          for(int i=0;i<d.size();i++){

             res[d[i].first-minLevel].push_back(d[i].second);


          }

          return res; 
    }
};

I submit get this

🔸Final Correct Approach (Working)

Than i realize i have to manage depth also to make it in order way
so i again added a depth also in vector<pair<pair<level<depth,value»>

class Solution {
public:
     void view(TreeNode* root,int level,int depth,vector<pair<int,pair<int,int>>>&d){
        if(root==NULL)return;

        d.push_back({level,{depth,root->val}});

        view(root->left,level-1,depth+1,d);
        view(root->right,level+1,depth+1,d);
     }
    vector<vector<int>> verticalTraversal(TreeNode* root) {

          vector<pair<int,pair<int,int>>> d;
          view(root,0,0,d);

          if (d.empty()) return {};

          sort(d.begin(),d.end());



          int minLevel = d.front().first;
          int maxLevel = d.back().first;
          int size = maxLevel - minLevel + 1;
          vector<vector<int>> res(size);
          for(int i=0;i<d.size();i++){

             res[d[i].first-minLevel].push_back(d[i].second.second);


          }

          return res;

    }
};

🔸 Optional Extras

You can also add:

• How this relates to level-order and inorder traversal.

• Time complexity: O(N log N) due to sorting.

• Why map or priority_queue-based solutions also work. find in Leetcode solutions this approach