2
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$
    – Raphael
    Mar 19 '14 at 15:24
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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