Print bottom view of a binary tree

Problem Detail: 

For a binary tree we define horizontal distance as follows:

    Horizontal distance(hd) of root = 0     If you go left then hd = hd(of its parent)-1, and      if you go right then hd = hd(of its parent)+1. 

The bottom view of a tree then consists of all the nodes of the tree, where there is no node with the same hd and a greater level. (There may be multiple such nodes for a given value of hd. In this case all of them belong to the bottom view.) I'm looking for an algorithm that outputs the bottom view of a tree.

---

Examples:

Suppose the binary tree is:

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

Bottom view of the tree is: 4 2 5 6 8 7

    Ok so for the first example,     Horizontal distance of node with value 1: 0, level = 1     Horizontal distance of node with value 2: 0 - 1 = -1, level = 2     Horizontal distance of node with value 3: 0 + 1 = 1, level = 2     Horizontal distance of node with value 4: -1 - 1 = -2, level = 3     Horizontal distance of node with value 5: -1 + 1 = 0, level = 3     Horizontal distance of node with value 6: 1 - 1 = 0, level = 3     Horizontal distance of node with value 7: 1 + 1 = 2, level = 3     Horizontal distance of node with value 8: 0 + 1 = 1, level = 4      So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.     So for hd = -2, print 4     for hd = -1, print 2     for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line     for hd = 1, print 8     for hd = 2, print 7 

One more example for reference :

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

So the output for this will be : 8 4 9 10 12 5 6 11 13 14 7 15

Similarly for this example hd of node with value 1: 0, , level = 1 hd of node with value 2: -1, level = 2 hd of node with value 3: 1, level = 2 hd of node with value 4: -2, level = 3 hd of node with value 5: 0, , level = 3 hd of node with value 6: 0, level = 3 hd of node with value 7: 2, level = 3 hd of node with value 8: -3, level = 4 hd of node with value 9: -1, level = 4 hd of node with value 10: -1, level = 4 hd of node with value 11: 1, level = 4 hd of node with value 12: -1, level = 4 hd of node with value 13: 1, level = 4 hd of node with value 14: 1, level = 4 hd of node with value 15: 3, level = 4  So, the output will be: hd = -3, print 8 hd = -2, print 4 hd = -1, print 9 10 12 hd = 0, print 5 6 hd = 1, print 11 13 14 hd = 2, print 7 hd = 3, print 15   So the ouput will be: 8 4 9 10 12 5 6 11 13 14 7 15 

---

I already know a method in which I can do it using a lot of extra space (a map, and a 1-D array for storing the level of the last element in that vertical line) and with time complexity of $O(N \log N)$. And this is the implementation of this method:

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l) {      if(node == NULL)              return;      if(level == 1){               if(lev[hd-min] == 0 || lev[hd-min] == l){                       lev[hd-min] = l;                       visited[hd-min].push_back(node->data);               }      }      else if(level > 1)      {           printBottom(node->left, level-1, hd-1, min, visited, lev, l);           printBottom(node->right, level-1, hd+1, min, visited, lev, l);      } }   int main() {     find the minimum and maximum values for hd via DFS      int lev[max-min+1]; //lev[hd] contains the maximum level for which we have found nodes with this value of hd; initialized with 0's      map < int, vector<int> > visited; //the nodes in the bottom view      int h = height(root);      for (int i=h; i>0; i--){         printBottom(root, i, 0, min, visited, lev, i);     }      output visited } 

I am seeking help to do this in more optimized way, which used less space or time. Is there any other efficient method for this problem?

Asked By : shalki

Answered By : FrankW

First, you can get the time complexity down to ${\cal O}(n)$, while keeping the same space complexity. You can do this by filling visited in a single run of printBottom:

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[]) {      if(node == NULL)              return;      if(lev[hd-min] < level){          lev[hd-min] = level;          visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node      }      if(lev[hd-min] <= level){          visited[hd-min].push_back(node->data);      }      printBottom(node->left, level+1, hd-1, min, visited, lev);      printBottom(node->right, level+1, hd+1, min, visited, lev); } 

with the initial call printBottom(root, 1, 0, min, visited, lev);

If you insist on the nodes beig output in order of increasing value of hd, I don't think you can improve space consumption. However, if you allow a different order of output, you can get rid of visited, by first determining for each value of 'hd', which level should be output and then making another pass, printing the values that match:

void fillLev(Node *node, int level, int hd, int min, int lev[]) {      if(node == NULL)              return;      if(lev[hd-min] < level){          lev[hd-min] = level;      }      fillLev(node->left, level+1, hd-1, min, lev);      fillLev(node->right, level+1, hd+1, min, lev); } void printBottom(Node *node, int level, int hd, int min, int lev[]) {      if(node == NULL)              return;      if(lev[hd-min] == level){          cout << node->data;      }      printBottom(node->left, level+1, hd-1, min, lev);      printBottom(node->right, level+1, hd+1, min, lev); } 

with calls fillLev(root, 1, 0, min, lev); and printBottom(root, 1, 0, min, lev);.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22801