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

Answer 1

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