Java print top view of binary search tree

Question

Question given: Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree.

This is the code I have written for top view of tree. My code is running for some cases only . I want to know what is wrong in the code that I have written .

My concept was that to give index to each node and only first node that gets a particular index will be printed .

 public static void rhs(Node root,int index,ArrayList list){
        if(root==null){
            return;
        }
        for (int i=0;i<list.size();i++){
            if (index==list.get(i)){
               rhs(root.left,index-1,list);
               rhs(root.right,index+1,list);
               return;
            }
        }
         System.out.print(root.data+" ");
                list.add(index);
                rhs(root.left,index-1,list);
                rhs(root.right,index+1,list); 
    }

public static void topView(Node root) {
    if (root==null){
        return;
    }
    ArrayList<Integer> list=new ArrayList<>();
    list.add(0);
 
    System.out.print(root.data+" ");

    rhs(root.left,-1,list);
  
    rhs(root.right,1,list);         


}

One of the case it wasn't working for was -

15
1 14 3 7 4 5 15 6 13 10 11 2 12 8 9

ouput expected (sequence doesn't matter):

2 1 14 15 12

my output:

1 14 2 6 12

already predefined which cannot be changed-

public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    Node root = null;
    while(t-- > 0) {
        int data = scan.nextInt();
        root = insert(root, data);
    }
    scan.close();
    topView(root);
}   

}

Answer 1

The problem with your code is that it assumes that when you get to a certain index the first time, that this will also be with the value that will be visible from the top. This surely is true at that moment, but it could happen that a node that is visited later might end up at the same index, and be higher up in the tree, therefore hiding the previously visible node.

Here is a small example:

index:   -1  0  1

tree:        4
            / \
           1   5
            \
             2
              \
               3
              

For this tree, your algorithm will first process the left sub tree of the root, and so it will visit 3 before 5, and so you'll output "3" for index 1.

So, to fix this, you should actually refrain from outputting anything, until you have traversed the whole tree. While traversing associate a value and depth with each index (using a Map maybe), and update the associated value when you have a new candidate with a lesser depth value.