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

Meaghan

Your problem is with your recursion. You ideally only want to traverse both left and right from the root node. And once down, you either want to keep going left or keep going right. But while using recursion you are traversing both left and right on all the nodes. That's wrong. Just walk through your code manually, you will know the mistakes. – Secondbest

Kindly see my solution, at least give a reaction. – Pulmotor

@Meaghan Kindly point out the reason you have not selected any answers yet. – Pulmotor

@Meaghan Selecting an answer means that this answer solved your problem in the best way. – Pulmotor

@Meaghan This will also encourage users to answer your new questions. – Pulmotor

@Dante I thought I had already accepted your answer. Really sorry! – Meaghan

@Dante I have solved it using arrayList. What do you think about this approach, I mean in terms of space complexity and time complexity. I have just started programming. I don't know which approach is the best. – Meaghan

@Meaghan I cannot comment unless i see the code. – Pulmotor

@Dante I have given the link in pastie in the above comment, under the name arrayList .. anyways here is the link : pastie.org/10303572 – Meaghan

@Meaghan Its linear and effieient.Good. – Pulmotor

@Dante last question, don't you think that's too many lines of code? – Meaghan

@Dante Always focus on time and space and complexity. – Pulmotor

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

Pulmotor

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 – Ill

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

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

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

Abbott

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. – Ill

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

Horizontal distance of 8 would be 1, not 0 – Ellsworthellwood

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


}

Manzanares

Answer 4

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

Configuration

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. – Edom

Answer 5

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

Harwin

Add some more description here – Glarus

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

Answer 6

My Java implementation is attached. The left side of the tree is more interesting if solved recursively, but reversing the string(my way below) was easier and only required the use of one method.

public void top_view(Node root){

    String output = "";

    Node left = root.left;
    Node right = root.right;

    String leftOutput = "";
    while(left != null){
        leftOutput += left.data + " ";
        left = left.left;
    }

    String left = "";
    for(int i = leftOutput.length - 1; i >= 0; i--){
        left += leftOutput.substring(i, i+1);
    }

    output += left;

    output += " " + root.data + " ";

    while(right != null){
        output += right.data + " ";
        right = right.right;
    }

    output = output.substring(1, output.length());
    System.out.println(output);
}

Osiris

Answer 7

void top_view(Node root)    
{    
    if(root.left!=null) top_view(root.left);   

    if(root.left!=null || root.right!=null)
         System.out.print(root.data + " ");

    if(root.right!=null) top_view(root.right);        
}

Clatter

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

Answer 8

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<<p->data<<" ";
    }
}
void right_array(node *p)
{
    if(p==NULL)
    return;
    else
    {
        cout<<p->data<<" ";
        right_array(p->right);
    }

}
void top_view(node * root)
{   int i=0;
node *t1=root;
node *t2=root;
    left_array(t2);
    right_array(t1->right);

}`

Teutonic

Answer 9

A very simple recursive solution which takes care of long branches of the child node. This is solved using horizontal distance concept.

public void printTopView(BNode root) {
        Map<Integer, Integer> data = new TreeMap<Integer, Integer>();
        printTopViewRecursive(data, root, 0);
        for(int key : data.keySet()) {
            System.out.print(data.get(key) +" ");
        }
    }


    private void printTopViewRecursive(Map<Integer, Integer> hDMap, BNode root, int hD) {
        if(root == null)
            return;
        if(!hDMap.containsKey(hD)) {
            hDMap.put(hD, root.data);
        }
        printTopViewRecursive(hDMap, root.left,hD - 1);
        printTopViewRecursive(hDMap, root.right, hD + 1);
    }

Reproduction

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); – Wickman

Answer 10

in java recursivish solution. converted from c++ code

void top_view(Node root)
{
    left_array(root);
    right_array(root.right);
}

void left_array(Node p)
{
    if(p==null)
        return;
    else
    {
        left_array(p.left);
        System.out.printf("%d ",p.data);
    }
}
void right_array(Node p)
{
    if(p==null)
        return;
    else
    {
        System.out.printf("%d ",p.data);
        right_array(p.right);
    }
}

Bertrando

Answer 11

void top_view(Node root)
 {
    Node left = root;
    Node right = root;
    print_left(root.left);
    System.out.print(root.data + " ");
    print_right(root.right) ;
 }

void print_left(Node start)
 {
    if(start != null)
     {
       print_left(start.left);
       System.out.print(start.data + " "); 
     } 
 }

void print_right(Node start)
 {
    if(start != null)
    {
       System.out.print(start.data + " ");    
       print_right(start.right);
    }     
  } 

Azole

Answer 12

One simple recursive way to do it:

void top_view(Node root)
{
    print_top_view(root.left, "left");
    System.out.print(root.data  + " ");
    print_top_view(root.right, "right");
}

void print_top_view(Node root, String side) {
    if(side.equals("left")) {
        if(root.left != null) {
            print_top_view(root.left, "left"); 
        }
       System.out.print(root.data + " ");
    } else if(side.equals("right")) {
        System.out.print(root.data + " ");
        if(root.right != null) {
          print_top_view(root.right, "right");  
        } 
    }
}

Improve

Answer 13

if(root){
if(root->left !=NULL || root->right !=NULL){
    if(root->left)
        top_view(root->left);

     cout<<root->data<<" ";

     if(root->right)
        top_view(root->right);

}}

Landgrabber

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

Answer 14

This is the code for top-view of a binary tree in c++..

void topview(node* root,queue &Q)

{

if(!root)
    return;
map<int,int> TV;
Q.push(root);
TV[root->data]=0;
map<int,int>:: iterator it;
int min=INT_MAX,max=INT_MIN;
while(!Q.empty())
{
    node* temp =Q.front();
    Q.pop();
    int l=0;

    for(it=TV.begin();it!=TV.end();it++)
    {
        if(it->first==temp->data)
        {
            l=it->second;
           break;
        }

    }
    if(l<min) 
        {min=l;}
    if(l>max) 
        max=l;
    if(temp->left)
    {
        Q.push(temp->left);
        TV[temp->left->data] = l-1;
    }
    if(temp->right)
    {
        Q.push(temp->right);
        TV[temp->right->data] = l+1;
    }
}
cout<<max<<min<<endl;
for(int  i =min;i<=max;i++)
{
    for(it=TV.begin();it!=TV.end();it++)
    {
        if(it->second==i)
        {
            cout<<it->first;
            break;
        }
    }
}

}

void topview_aux(node* root)

{

queue<node*> Q;

topview(root,Q);

}

Frieze

Answer 15

A quite similar approach to the one @Karthik mentioned but with keeping the order, is to postpone the printing to the end and keep top view nodes ordered in double ended queue.

• We guarantee the order using BFS
• Each round we check if the current node's horizontal distance is larger than the maximum distance reached in the previous rounds (negative distance for left nodes).
• New top view nodes with -ve distance (left position) added to the left end of the deque , while right nodes with +ve distance added to the right end.

Sample solution in Java

import java.util.*;

class Node {
  int data;
  Node left;
  Node right;

  public Node(int data) {
    this.data = data;
  }
}

enum Position {
  ROOT,
  RIGHT,
  LEFT
}

class NodePositionDetails {
  Node node;
  // Node position in the tree
  Position pos;
  // horizontal distance from the root (-ve for left nodes)
  int hd;

  public NodePositionDetails(Node node, Position pos, int hd) {
    this.node = node;
    this.pos = pos;
    this.hd = hd;
  }
}

public class TreeTopView {
  public void topView(Node root) {
    // max horizontal distance reached in the right direction uptill the current round
    int reachedRightHD = 0;
    // max horizontal distance reached in the left direction uptill the current round
    int reachedLeftHD = 0;

    if (root == null)
      return;

    // queue for saving nodes for BFS
    Queue < NodePositionDetails > nodes = new LinkedList < > ();

    // Double ended queue to save the top view nodes in order
    Deque < Integer > topViewElements = new ArrayDeque < Integer > ();

    // adding root node to BFS queue 
    NodePositionDetails rootNode = new NodePositionDetails(root, Position.ROOT, 0);
    nodes.add(rootNode);

    while (!nodes.isEmpty()) {
      NodePositionDetails node = nodes.remove();

      // in the first round, Root node is added, later rounds left and right nodes handled in order depending on BFS. if the current horizontal distance is larger than the last largest horizontal distance (saved in reachedLeftHD and reachedRightHD)
      if (node.pos.equals(Position.LEFT) && node.hd == reachedLeftHD - 1) {
        topViewElements.addFirst(node.node.data);
        reachedLeftHD -= 1;
      } else if (node.pos.equals(Position.RIGHT) && node.hd == reachedRightHD + 1) {
        topViewElements.addLast(node.node.data);
        reachedRightHD += 1;
      } else if (node.pos.equals(Position.ROOT)) { // reachedLeftHD == 0 && reachedRightHD ==0
        topViewElements.addFirst(node.node.data);
      }

      // Normal BFS, adding left and right nodes to the queue
      if (node.node.left != null) {
        nodes.add(new NodePositionDetails(node.node.left, Position.LEFT, node.hd - 1));
      }
      if (node.node.right != null) {
        nodes.add(new NodePositionDetails(node.node.right, Position.RIGHT, node.hd + 1));
      }
    }

    // print top elements view
    for (Integer x: topViewElements) {
      System.out.print(x + " ");
    }
  }
}

And for testing:

  public static void main(String[] args) throws java.lang.Exception {
    /**
       Test Case 1 & 2
        1
       /  \
      2    3
     / \   
    7    4  
   /      \ 
  8        5
            \
             6

       Test Case 3: add long left branch under 3  (branch : left to the 3   3-> 8 -> 9 -> 10 -> 11

       **/

    Node root = new Node(1); //hd = 0
    // test Case 1 -- output: 2 1 3 6
    root.left = new Node(2); // hd = -1
    root.right = new Node(3); // hd = +1
    root.left.right = new Node(4); // hd = 0
    root.left.right.right = new Node(5); // hd = +1
    root.left.right.right.right = new Node(6); // hd = +2

    // test case 2 -- output: 8 7 2 1 3 6 
    root.left.left = new Node(7); // hd = -2
    root.left.left.left = new Node(8); // hd = -3

    // test case 3 -- output: 11 7 2 1 3 6 
    root.left.left.left = null;
    root.right.left = new Node(8); //hd = 0
    root.right.left.left = new Node(9); // hd = -1
    root.right.left.left.left = new Node(10); // hd = -2
    root.right.left.left.left.left = new Node(11); //hd = -3

    new TreeTopView().topView(root);
  }

Custer

Answer 16

Simplest Recursive Solution

void top_view(Node root)
{
 // For left side of the tree
    top_view_left(root);
 // For Right side of the tree
    top_view_right(root.right);
}

void top_view_left(Node root){
     if(root != null)
  {     
     // Postorder
     top_view_left(root.left);
     System.out.print(root.data + " ");
  }  
}

void top_view_right(Node root){
    if(root != null)
  {
        //  Preorder
      System.out.print(root.data + " ");
      top_view_right(root.right);
  }  
}

Ator

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

Answer 17

This:

import queue

class NodeWrap:
    def __init__(self, node, hd):
        self.node = node
        #horizontal distance
        self.hd = hd

def topView(root):
    d = {}
    q = queue.Queue()
    q.put(NodeWrap(root, 0))
    while not q.empty():
        node_wrap = q.get()
        node = node_wrap.node
        current_hd = node_wrap.hd
        if d.get(current_hd) is None:
            d[current_hd] = node
            print(node.info, end=" ")
        if node.left is not None:
            q.put(NodeWrap(node.left, current_hd - 1))
        if node.right is not None:
            q.put(NodeWrap(node.right, current_hd + 1))

has to be working solution on Python but for some reasons it fails on 6 test cases from 7 on hackerrank.com. Can somebody explain me why it is happening?

Those people who just run "left" and "right" functions don't understand the task.

Annulet

Answer 18

Python Solution

Solve using Breadth First Traversal

def topView(root):
    q = deque()
    #Adding root node to the deque along with its Horizontal Distance from root.
    q.append([root,0])
    
    #Dictionary to store the {Horizontal Distance: First Node that has this distance}
    s = {}
    
    #Breadth First Traversal - [To keep track of the first Node that is visited.]
    while q:
        temp = q.popleft()
        #Horizontal Distance from Root
        d = temp[1]
        
        #Adding the Left Child to the Queue (if Exists)
        if temp[0].left is not None:
            q.append([temp[0].left, d-1])
        
        #Adding the Right Child to the Queue (if Exists)
        if temp[0].right is not None:
            q.append([temp[0].right, d+1])
        
        #Adding the Horizontal Distance and the First Node that has this distance to Dictionary.
        if d not in s:
            s[d] = temp[0].info
    
    #Printing out the Top View of Tree based on the values in the Dictionary - From least to Highest Horizontal Distance from Root Node.
    for i in sorted(s):
        print(s[i], end=" ")

Hearse

Answer 19

def printTopView(root):

lst=[]
current1=root.left
while current1!=None:
    lst.append(current1.key)
    current1=current1.left
lst.reverse()
current2=root
while current2!=None:
    lst.append(current2.key)
    current2=current2.right

print(*lst)

Aggravate

Answer 20

Some of the answers above do not work. I tried commenting on them, but, apparently, I don't have the right score, since I've never tried to comment here before.

The problem is that you need to do a breadth first search of the tree to ensure the correct order of the nodes. To exclude "obscured" nodes, another website suggested ranking each node. The root is 0. All branches to the left of a node, have the parent rank, -1. All branches to the right have the parent rank +1. Any nodes with a duplicate rank of its ancestor are excluded.

Then print out the selected nodes in rank order. This will work in all cases.

Abcoulomb

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 – Evered