Leetcode.com problem 987: "Vertical-Order-Traversal-Of-A-Binary-Tree"

James S. Plank

• Problem Statement.
• Success Rate (as of September, 2022): 44.4%
• This is a hard problem.

• A skeleton with my main() that you can use to test your answer.
• A solution that includes the main() from skeleton.cpp.

In case Leetcode's servers are down

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Given the root of a binary tree, return the vertical order traversal of the tree.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution {
public:
    vector <vector <int> > verticalTraversal(TreeNode* root);
};

Examples

Answer: [[6],[3],[8]]

Answer: [[6],[3,5],[8]]

Answer: [[6],[3,2],[8]]

Answer: [[6],[3,2,5],[8]] Since 2 and 5 are both at (2,0), you sort them in the answer.

Hints

The solution is a combination of a depth-first search and a nested map. Let's concentrate on each in turn. The reason for the depth-first search is two-fold. First, it's the only way to visit all of the nodes. Second, it makes it easy, for each node, to label it with its row and column number.

So, inside the class definition, I defined the dfs:

void dfs(TreeNode *root, int r, int c);

The job of the dfs is to put the node into the main data structure (see below), and then to call the dfs recursively on the left and right subtrees.

Onto the main data structure. Here was its declaration, again inside of the Solution class:

map <int, map <int, multiset <int> > > V;

The first key is the column number. In that way, when you traverse the map, it will be from low column to high column. The second key is the row number. In that way, when you traverse the map for a given column, it will be from low row to high row. And finally, the inner data structure is a multiset. That's because multiple nodes can have the same (row,col) labeling, and you want to print them from low to high. We use a multiset instead of a set in case two nodes have the same val's.

Once you have the definitions in place, the rest of the code falls out pretty naturally:

/* I have added the dfs() method and the V data structure to the class definition. */

class Solution {
public:
    vector <vector <int> > verticalTraversal(TreeNode* root);
    void dfs(TreeNode *root, int r, int c);
    map <int, map <int, multiset <int> > > V;
};

/* The DFS is extemely straightforward.  I'll comment inline. */

void Solution::dfs(TreeNode *root, int r, int c)
{
  if (root == nullptr) return;      // If we're null, better return so you don't segfault.
  V[c][r].insert(root->val);        // Insert the node's val into the proper place in the main data structure.
  dfs(root->left, r+1, c-1);        // Recursively call the dfs on the left and right children.
  dfs(root->right, r+1, c+1);
}


/* The main method calls the dfs to set up the main data structure (V).
   Then it traverses that data structure to create the return vector. */

vector <vector <int> > Solution::verticalTraversal(TreeNode* root)
{
  vector < vector <int> > rv;
  map <int, map <int, multiset <int> > >::iterator vit;
  map <int, multiset <int> >::iterator mit;
  multiset <int>::iterator sit;
  int i;

  dfs(root, 0, 0);    // Call the dfs on the root, to create V

  i = 0;              // Traverse V to create the return value.
  for (vit = V.begin(); vit != V.end(); vit++) {
    rv.resize(i+1);
    for (mit = vit->second.begin(); mit != vit->second.end(); mit++) {
      for (sit = mit->second.begin(); sit != mit->second.end(); sit++) {
        rv[i].push_back(*sit);
      }
    }
    i++;
  }

  return rv;
}

The code and the main are in solution.cpp. Here are the examples:

UNIX> g++ solution.cpp
UNIX> echo 3 6 8 | ./a.out
6 
3 
8 
UNIX> echo 3 6 8 -1 5 | ./a.out
6 
3 5 
8 
UNIX> echo 3 6 8 -1 -1 2 | ./a.out
6 
3 2 
8 
UNIX> echo 3 6 8 -1 5 2 -1 | ./a.out
6 
3 2 5 
8 
UNIX> 

You could also use a deque -- something like

deque < map < int, multiset <int> > m;

Then, you can keep track of the minimum column in the class definition, and when you see a column that is one less than that, you update and call push_front().

Or perhaps:

deque < pair <int, int> > m;

Into the pair, you put the row number and the value, and then when you're done creating the deque, you sort it by row and then by value (write a custom comparison function). That may well be the most efficient way to solve the problem.