Charan Charan - 4 months ago 13
Java Question

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

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?

enter image description here enter image description here

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

Answer

This problem can be very easily solved by using:

Solution 1

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()+" ");
 }

I also solved this using recursion but my approach is entirely different from yours.This is how I did it

Solution 2

public void topview(Node root)
 {
     if(root==null)
      return;
     traverse_left(root.left);
     System.out.print(root.data+" ");
     traverse_right(root.right);
 }
 public void traverse_left(Node x)
 {
     if(x==null)
      return;
     traverse_left(x.left);
      System.out.print(x.data+"  ");
 }
 public void traverse_right(Node x)
 {
     if(x==null)
      return;
     System.out.print(x.data+"  ");
     traverse_right(x.right);     
 } 

Your approach that you decided to do this using Recursion is good because it has space complexity of O(1), whereas the iterative has space complexity of O(n).But of course recursion makes an extra burden on the stack of your program process.

Comments