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 Top View of a Binary Tree

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

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

Print-The-Top-View-of-a-Binary-Tree.1

Print-The-Top-View-of-a-Binary-Tree.1

as you can see in the exam­ple above,8, 4, 2, 1, 3, 7 is the Top 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. Just mod­i­fied the code so that it will print only the first ele­ment it will encounter in the ver­ti­cal order.

How will you know that you are vis­it­ing the first node at every level?

  • 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.
  • Vertical-Order-Sum-Implementation

    Vertical-Order-Sum-Implementation

  • Now all we need to do the level order tra­ver­sal just to ensure that we will visit the top most node at level before we visit any other node at that 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.
  • See the code for bet­ter understanding.

Com­plete Code:


Out­put:

 1   2   3   4   7   8   

 

Ref­er­ence: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

Thanks OP for find­ing out the mis­take in ear­lier code.

You may also like...

  • Pingback: Revo()

  • OP

    I am sorry but it seems to be wrong. it wont work on not “well ordered” tree, like:

    1
    /
    2 3

    4

    5

    6

    it will print 2,1,5,6 instead of 2,1,3,6

    • Sumit

      Thanks OP for find­ing out the error. I have cor­rected the code. Please do let me know if you find errors in other posts.

  • Ramesh Babu Y

    very good expla­na­tion , thanks Sumit . go head

    • tuto­ri­al­hori­zon

      Thanks Ramesh

  • Ramesh Babu Y

    In your code ,

    // add the left and right chil­dren of vis­it­ing 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));

    }

    it is wrong , because when we are mov­ing left we must add that is level++ , but your code is doing level– and same type if issue when we are mov­ing right side

    please cor­rect the code

    • tuto­ri­al­hori­zon

      Ramesh, lev­els are just way to dif­fer­en­ti­ate the ver­ti­cal orders. It does not mat­ter while mov­ing left you do level++ or level–. Its just that it should be oppo­site to what you do on the right side. We will get the same result by chang­ing the code. Just see the dia­gram where lev­els are dif­fer­en­ti­ated.
      Please revert back if needed more clar­i­fi­ca­tion or have fur­ther queries.

  • Jag­mo­han Singh

    A sim­pler approach in C++

    // print­ing top view of the tree

    void left_array(node *p)

    {

    if(p==NULL)

    return;

    else

    {

    left_array(p->left);

    cout<data«” “;

    }

    }

    void right_array(node *p)

    {

    if(p==NULL)

    return;

    else

    {

    cout<data<right);

    }

    }

    void top_view(node * root) // Call this func­tion from main

    { int i=0;

    node *t1=root;

    node *t2=root;

    left_array(t2);

    right_array(t1->right);

    }

    • Suman Sourav Singh

      your solu­tion isnt com­pletely correct.