Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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:

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

struct Node{
       int data;
       struct Node *left, *right;
};

Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int height(Node *node)
{
    if(node == NULL)
            return 0;
    else{
         int lh = height(node->left);
         int rh = height(node->right);

         if(lh > rh)
               return (lh+1);
         else
               return (rh+1);
    }
}

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);
     }
}

void findMinMax(Node *node, int *min, int *max, int hd)
{
     if(node == NULL)
             return;

     if(hd < *min)
          *min = hd;
     else if(hd > *max)
          *max = hd;

     findMinMax(node->left, min, max, hd-1);
     findMinMax(node->right, min, max, hd+1);
}

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->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(11);
    root->right->left->left = newNode(12);
    root->right->left->right = newNode(13);
    root->right->right->left = newNode(14);
    root->right->right->right = newNode(15);

    int min = 0, max = 0;

    findMinMax(root, &min, &max, 0);

    int lev[max-min+1];
    map < int, vector<int> > visited;
    map< int,vector<int> > :: iterator it;

    for(int i = 0; i < max-min+1; i++)
            lev[i] = 0;

    int h = height(root);

    for (int i=h; i>0; i--){
        printBottom(root, i, 0, min, visited, lev, i);
    }

    for(it = visited.begin() ; it != visited.end() ; it++) {
        for(int i=0 ; i < it->second.size() ; i++) {
            cout << it->second[i] << " ";
        }
    }

    return 0;
}

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?

share|improve this question
2  
Why don't you try recursing the entire tree, and for every leaf node, re-tracing its value through the binary tree (as if you were going to insert it) and verify that you arrive at the same leaf node. –  Neil Mar 19 at 10:58
    
I am not able to get your approach. Please can you be more clear about it. –  shalki Mar 19 at 11:10
    
And there can also be a non-leaf node in the bottom view of tree as you could see in my additional example. –  shalki Mar 19 at 11:42
    
Well this isn't a solution to your problem, which is why I'm not posting it as a solution. However, you can know if a binary tree is correct by, for every node in the tree, seeing where it would fall if you were to insert it, and ensure that it is in the proper position. If not, it is not a valid binary tree. –  Neil Mar 19 at 11:55
1  
Would this be better if it were migrated to CodeReview? codereview.stackexchange.com/questions –  FrustratedWithFormsDesigner Mar 19 at 14:25

3 Answers 3

First create a list, indexed by vertical line, recording the maximum level found on that line. Walk the tree one time to fill in this list.

At this point every list[vertical] entry contains the level that can be seen in the bottom view of the tree.

Then walk the tree again, printing out each node whose level matches the maximum found on its line.

int MaxLvl[];

void printBotOne( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotOne(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]<Level then MaxLvl[Column] = Level;
    printBotOne(qNode->right, Level+1, Column+1);
  }
}

void printBotTwo( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotTwo(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]==Level then cout << qNode->data << " ";
    printBotTwo(qNode->right, Level+1, Column+1);
  }
}

void printBottom( node *qNode ) {
  for(int II = 0; II<nodecount; II++) MaxLvl[II] = 0;
  printBotOne(qNode, 0, nodecount/2);
  printBotTwo(qNode, 0, nodecount/2);
}

This requires a 1D array and runs in O(N).

share|improve this answer
    
Hi, is there any other optimized and space efficient method. I already implemented this one, but in this I will need a lot of memory(an array of list and a 1-D array), and it will take O(NlogN) time also. Is there any other method? –  shalki Mar 20 at 6:22
    
The answer is now completely clear I have given additional instructions. –  A. I. Breveleri Mar 20 at 16:25
    
Yes. It is one of the solution, but this will increase time complexity to O(N^2). I am seeking for much better solution if anyone could come out with it. Anyways thanks for pointing this out. –  shalki Mar 21 at 8:11
    
I have coded it for you but please check my grammar as I do not have a C++ compiler available. Visiting every node in a tree is O(NodeCount). Doing it twice is still O(NodeCount). –  A. I. Breveleri Mar 21 at 13:42
    
You are correct at your level. But this solution won't print it in the correct order. See the answer here: I posted it on cs.stackexchange first but someone told to post it here too. So, I posted here also. The answer given by @FrankW here is correct. –  shalki Mar 21 at 16:06

There are still some things about your question that are unclear, but it seems like your rule for "bottom" is a node that does not have grandchildren. The following function will print all nodes that meet this definition of bottom:

// Print out nodes that don't have grandchildren
void printBottom2(Node *root)
{
    if (root->left) {
        // recursive call for left child
        printBottom2(root->left);
    }

    // check for grand children of this node:
    if (
         // left isn't present or has no children
         ( !root->left || ( !root->left->left && !root->left->right ) ) 
         &&
         // right isn't present or has no children
         ( !root->right || ( !root->right->left && !root->right->right) )
       )
    {
        // Since there is no child of left or right, print data:
        cout << root->data << " ";
    }

    if (root->right) {
        // recursive call for right child
        printBottom2(root->right);
    }
}

You can display the full bottom of a tree by calling printBottom2 with just the root node: printBottom2(root); in your code above.

share|improve this answer
    
Hey your solution won't work. I have explained the examples more clearly now. Please see it again and help me with it. Thanks for you help. –  shalki Mar 20 at 4:19
up vote 0 down vote accepted

First, you can get the time complexity down to 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);.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.