Trying to print top view of a tree using two if statements

Question

Problem Statement

You are given a pointer to the root of a binary tree. Print the top view of the binary tree. You only have to complete the function.

My Code:

void top_view(Node root)
 {  
       Node r = root;

       if(r.left!=null){
          top_view(r.left);
          System.out.print(r.data + " ");
        }
       if(r.right!=null){
          System.out.print(r.data + " ");
          top_view(r.right);
        }
}

The two if statements are executed every time the function is called, but I need only one of them to execute. I tried switch but its giving constant expression error. I have already found a different solution for this problem.

So I only want to know if we can make only one if execute at a time i.e, is there a way to fix my code without changing the approach?

Problem link: https://www.hackerrank.com/challenges/tree-top-view

Solution 1

This problem can be very easily solved by using:

Stack: To print the root and the left subtree.

Queue: To print the right subtree.

Your function should be like this:

 void topview(Node root)
 {
     if(root==null)
      return;
     Stack<Integer> s=new Stack<Integer>();
     s.push(root.data);
     Node root2=root;
     while(root.left!=null)
     {
      s.push(root.left.data);
      root=root.left;
     }
     while(s.size()!=0)
      System.out.print(s.pop()+" ");

     Queue<Integer> q=new LinkedList<Integer>(); 
     q.add(root2.right.data);
     root2=root2.right;     
     while(root2.right!=null)
     {
      q.add(root2.right.data);
      root2=root2.right;
     }
     while(q.size()!=0)
      System.out.print(q.poll()+" ");
 }

Solution 2

Your approach will work not because, when you call left or right subtree you will just stick to it. The problem with this approach is you are just driven by which side of the tree is called first.

May be you can solve it by using stack and queue as somebody else said but i feel that the following is a simpler and more intuitive approach:

(SEE THE CODE AT THE END, IT'S VERY SIMPLE)

The approach to solve this is by maintaining horizontal distance from root and you print the first node for each different horizontal distance.

What is horizontal distance?

I am just taking the image you have added.

Horizontal distance for a particular node is defined as the number of from root horizontally. If you see no.of edges that will become vertical distance.

To make things easier for all the nodes on left side of root start with negative horizontal distance and right side positive distance.

How do you calculate horizontal distance?

If you are going right add 1, if you are going left add -1.

so

    horizontal distance of 3 = 0
    
    horizontal distance of 5 = -1
    horizontal distance of 1 = -2
    horizontal distance of 9 = -1
    horizontal distance of 4 = 0

    horizontal distance of 2 =  1
    horizontal distance of 6 =  0
    horizontal distance of 7 =  2
    horizontal distance of 8 =  1

Nodes 3,4,6 have same horizontal distance of 0 what does the mean?

That means when you see from top all these nodes are in a line vertically one above it.

If they are in a line vertically which one do you see?

The one which is can be reached first from root.

How do you find which one can be reached first?

as usual BFS

How this prints solution for your example?

There are five different horizontal distance value {-1,-2,0,1,2}

hor dist        Nodes

   0      - {3,6,8} // 3 comes first in BFS so print 3
  -1      - {5,9}   // 5 comes first in BFS so print 5
  -2      - {1}     // just print 1
   1      - {2}     // just print 2
   2      - {7}     // just print 7

So it will print {3,5,1,2,7}

HashSet<Integer> set = new HashSet<>();
Queue<QueueItem> queue = new LinkedList<>();
queue.add(new QueueItem(root, 0)); // Horizontal distance of root is 0

while (!queue.isEmpty())
{
    QueueItem temp = queue.poll();
    int hd = temp.hd;
    TreeNode n = temp.node;

    // If this is the first node at its horizontal distance,
    // then this node is in top view
    if (!set.contains(hd))
    {
        set.add(hd);
        System.out.print(n.key + " ");
    }

    if (n.left != null)
        queue.add(new QueueItem(n.left, hd-1));
    if (n.right != null)
        queue.add(new QueueItem(n.right, hd+1));
}
    

Solution 3

The solution is pretty easy if you print the left side by recursion and the right side using a simple while loop..

 void for_left(node *root)
{
    if(!root->left)
        {
        cout<<root->data<<" ";
        return;
    }
    for_left(root->left);
    cout<<root->data<<" ";
    return;

}

void top_view(node * root)
{
    for_left(root->left);
    cout<<root->data<<" ";
    while(root->right)
        {
        cout<<(root->right)->data<<" ";
        root=root->right;
    }


}

Solution 4

The solution can be found here - Git hub URL

Note that whatever the hackerrank question is with respect to balanced tree, if the tree is in the imbalanced state like below

    1
  /   \
2       3
  \   
    4  
      \
        5
         \
           6

For these kind of trees some complicated logic is required which is defined in geeksforgeeks here - GeeksforGeeks

Solution 5

This one actually works. Doesn't need a queue, but uses a stack in order to backtrack from the left side, since we don't have reference to the parent.

void top_view(Node root)
{
    Stack<Node> p = new Stack<Node>();
    Node current = root;
    while (current != null) 
    {
        p.push(current);
        current = current.left;
    }

    while (p.peek() != root) 
    {
        System.out.print(p.pop().data + " ");
    }

    current = root;
    while (current != null) 
    {
        System.out.print(current.data + " ");
        current = current.right;
    }
}

View more solutions

Comments

[Dinesh]

I think your code will produce output as {3, 5, 2, 1, 7} since the key is first displayed and then added to the queue. So the root will be displayed first.

[Dinesh]

This solution will not work if the tree has long branches from the left extending to the right or vice versa. See hackerrank.com/challenges/tree-top-view/forum/comments/59414

[Karthik]

the output does not need to be in the same order, all that matters is the the elements.

[Narendra Jaggi]

it will work for the second example geeksforgeeks.org/print-nodes-top-view-binary-tree

[aashah7]

This is exactly what I was looking for! +1!

[Arpit Ratan]

This solution is not correct. Posted a very simple recursive solution for this problem.

[triandicAnt]

Horizontal distance of 8 would be 1, not 0

[K Erlandsson]

Please provide an explanation about how your code works and how it solves the problem.

[maxomax]

This solution doesn't work for this example :- TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(10); root.left.right = new TreeNode(4); root.left.right.right = new TreeNode(5); root.left.right.right.right = new TreeNode(6); root.right.left = new TreeNode(11); root.right.left.right = new TreeNode(12); root.right.left.right.right = new TreeNode(13); root.right.left.right.right.right = new TreeNode(14);

[Cyclotron3x3]

This will not work. Imagine going one level left and then 5 levels to the right of that left. You see its breaking

[Ankit Kumar]

This solution will not work in all cases. it assumes that leaves branching out of internal nodes are never visible from top which is not true.

[Mathews Sunny]

Add some more description here

[Neha Chaudhary]

I will say that this is the best answer for this question. I wasn't able to think about a testcase like this.

[bhucho]

it is ok, to give answers but you need 50 reputation or so to comment, try to avoid writing the stories about some other person's answers, though we appreciate you sharing answers --FROM REVIEW