How you print bottom view of binary tree?

must

#1

How you print bottom view of binary tree?


#2

package BottomViewOfBT;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;

public class BottomViewOfBT {
public static TreeMap<Integer, Integer> ht = new TreeMap<>();;

public static void bottomView(Node root, int level) {
	if (root == null)
		return;
	// create a queue for level order traversal
	Queue<QueuePack> queue = new LinkedList<>();
	// add root with level 0 (create a queue item pack)
	queue.add(new QueuePack(level, root));
	while (!queue.isEmpty()) {
		QueuePack q = queue.remove();
		// take out the items from the package
		Node tnode = q.tnode;
		int lvl = q.level;

		// keep updating the Map so that it will have the last entry from
		// each level(vertically) and that will the bottom view of the tree
		ht.put(lvl, tnode.data);

		// add the left and right children of visiting nodes to the queue
		if (tnode.left != null) {
			queue.add(new QueuePack(lvl - 1, tnode.left));
		}
		if (tnode.right != null) {
			queue.add(new QueuePack(lvl + 1, tnode.right));
		}
	}

}

public static void display() { // print the bottom view.
	Set<Integer> keys = ht.keySet();
	for (Integer key : keys) {
		System.out.print(ht.get(key) + " ");
	}

}

public static void main(String[] args) {
	Node root = new Node(1);
	root.left = new Node(2);
	root.right = new Node(3);
	root.left.left = new Node(4);
	root.left.right = new Node(5);
	root.left.right.left = new Node(6);
	root.left.right.right = new Node(7);
	root.right.right = new Node(8);
	// root.right.right.left = new Node(30);

	bottomView(root, 0);
	display();
}

}

class Node {
int data;
Node left;
Node right;

public Node(int data) {
	this.data = data;
	left = null;
	right = null;
}

}

// this class’ represents the items stored in queue (used for level order
// traversal). Objects will store the nodes and its level
class QueuePack {
int level;
Node tnode;

public QueuePack(int level, Node tnode) {
	this.level = level;
	this.tnode = tnode;
}

}


#4

program to print bottom view of a binary tree

#include
#include
#include
#include

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 >& 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;

}