Print The Top View of a Binary Tree

Objective: 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 example below.

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

as you can see in the example above,8, 4, 2, 1, 3, 7 is the Top view of the given binary tree.

Approach:

This Approach is quite similar to the Print the Binary Tree in Vertical Order Path. Just modified the code so that it will print only the first element it will encounter in the vertical order.

How will you know that you are visiting 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
  • Now all we need to do the level order traversal 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 simple queue technique for level order traversal or BFS.
  • we will create a class QueuePack, this will store the objects containing node and its level.
  • See the code for better understanding.

Complete Code:

import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;
public class TopViewBT {
public static TreeMap<Integer, Integer> ht = new TreeMap<>();;
public void topView(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;
// check if this is the first node you are visiting at the level
if (ht.containsKey(lvl)) {
} else {// print it, its the first element at his level
System.out.print(tnode.data + " ");
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 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.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
TopViewBT p = new TopViewBT();
p.topView(root, 0);
}
}
//node structure of tree
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;
}
}

view raw
TopViewBT.java
hosted with ❤ by GitHub


Output:

 1   2   3   4   7   8   

 

Reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

11 thoughts on “Print The Top View of a Binary Tree”

  1. Pingback: Revo
  2. 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

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

      Reply
  3. In your code ,

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

    }

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

    please correct the code

    Reply
    • Ramesh, levels are just way to differentiate the vertical orders. It does not matter while moving left you do level++ or level–. Its just that it should be opposite to what you do on the right side. We will get the same result by changing the code. Just see the diagram where levels are differentiated.
      Please revert back if needed more clarification or have further queries.

      Reply
  4. A simpler approach in C++

    // printing 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 function from main

    { int i=0;

    node *t1=root;

    node *t2=root;

    left_array(t2);

    right_array(t1->right);

    }

    Reply

Leave a Reply to Suman Sourav Singh Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.