Print bottom view of a binary tree

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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