Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Print the Bottom View of the Binary Tree.

Objec­tive: - Given a binary tree, print it in Bot­tom View of it.

What is Bot­tom View: Bot­tom view means when you look the tree from the bot­tom the nodes you will see will be called the bot­tom view of the tree. See the exam­ple below.

Bottom-View-of-a-Binary-Tree

Bottom-View-of-a-Binary-Tree

as you can see in the exam­ple above,8, 4, 9, 5, 3, 7 is the bot­tom view of the given binary tree.

Approach:

This Approach is quite sim­i­lar to the - Print the Binary Tree in Ver­ti­cal Order Path.
and Print The Top View of a Binary Tree. Just mod­i­fied the code so that it will print only the last ele­ment it will encounter in the ver­ti­cal order. That will be the bot­tom view.

How will you know that you are vis­it­ing the last node at every level(Vertically)?

  • Take a vari­able called level, when­ever you go left, do level++ AND when­ever you go right do level–.
  • With step above we have sep­a­rated out the lev­els vertically.
  • level distribution

    level dis­tri­b­u­tion

  • Now you need to store the ele­ments of each level, so cre­ate a TreeMap and the (key,value) pair will be (level,element at that level).
  • Now all we need to do the level order tra­ver­sal and store only recent vis­ited node at each level(vertically), this way you will be stor­ing only the last ele­ment at each level.
  • We will use sim­ple queue tech­nique for level order tra­ver­sal or BFS.
  • we will cre­ate a class QueuePack, this will store the objects con­tain­ing node and its level.
  • At the end tra­verse through TreeMap and print all the val­ues in it, it will be the bot­tom view of a tree.
  • See the code for bet­ter understanding.

Code:

Output:
4 6 5 7 8 

 

You may also like...

  • Xiaozhen Zhong

    how would the tpre-order tra­verse guar­an­tee most recent vis­ited node would be at “bot­tom” of a ver­ti­cal level?
    Would fol­low­ing sequence work?
    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.left.right.right.right = new Node(9); ==> add another right node, which will be at same ver­ti­cal level of node(8) but lower.
    root.right.right = new Node(8);
    We should get 4 6 5 7 9 as bot­tom view, but my guess is the code will return 4 6 5 7 8 (wrong result)

    • tuto­ri­al­hori­zon

      Hi Xiaozhen,

      Code is cor­rect and will return 4 6 5 7 9, don’t con­cen­trate on pre­order tra­ver­sal, we are stor­ing the node at each ver­ti­cal level in a hash map ( in fact we are updat­ing it so hash map will con­tain the last node vis­ited at that level) See the diagram.

  • http://www.waytocrack.com kumar
  • Sub­odh Karwa

    Can you please explain how 5 and 6 both being at level –0 are printed using the code ?

  • suvro

    Print In-Order nodes where either left or right child is NULL

    pri­vate sta­tic void printBottomView(Tree tree) {

    if(tree==null)
    return;
    printBottomView(tree.leftChild);
    if(tree.leftChild==null||tree.rightChild==null)
    System.out.println(“===”+tree.data+”===”);
    printBottomView(tree.rightChild);
    }