Failed test cases in "Tree bottom view" problem

#1

THE FOLLOWING CODE IS PASSING ONLY TWO TEST CASES. I AM UNABLE TO FIND WHAT IS THE ERROR. PLEASE HELP ME.

import java.util.*;
public class Main
{
static class Node
{
int data;
Node left, right;
Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
Node root;
HashMap<Integer,Integer> map=new HashMap<>();
public Node insertLevelOrder(ArrayList arr, Node root,int i,int path)
{
if (i < arr.size()) {
Node temp = new Node(arr.get(i));
root = temp;
if(temp.data!=(-1))
map.put(path,temp.data);

        root.left = insertLevelOrder(arr, root.left,2 * i + 1,path-1); 

        root.right = insertLevelOrder(arr, root.right, 2 * i + 2,path+1); 
    }
    return root; 
} 

public void display(Node node)
{
    String str="";
    if(node.left!=null)
        str=str+node.left.data+"=>";
    else
        str=str+"END=>";
    str=str+node.data;
    if(node.right!=null)
        str=str+"<=" + node.right.data;
    else
        str=str+"<=END";
    System.out.println(str);
    if(node.left!=null)
            this.display(node.left);
    if(node.right!=null)
            this.display(node.right);
}

public static void main(String args[]) throws Exception
{ 
    Main tree = new Main(); 
    Scanner sc=new Scanner(System.in);
    
    ArrayList<Integer> list=new ArrayList<>();
    int node=0,nnode=0;
    while(nnode!=(node+1))
    {
        int n=sc.nextInt();
        if(n==-1)
        {
            list.add(n);
            nnode++;
        }
        else
        {
            list.add(n);
            node++;
        }
    }
    tree.root=tree.insertLevelOrder(list,tree.root,0,0);
    ArrayList<Integer> ans=new ArrayList<>(tree.map.keySet());
    ans.sort(null);
    for(int k=0;k<ans.size();k++)
        System.out.print(tree.map.get(ans.get(k))+" ");
}

}

#2

@vinay86048,
I am not able to understand how you are traversing the tree and getting the nodes.

Suggested approach:

  • The idea here is to observe that, if we try to see a tree from its bottom, then only the nodes which are at bottom in vertical order will be seen.
  • Start BFS from root. Maintain a queue of pairs comprising of node(Node *) type and vertical distance of node from root. Also, maintain a map which should store the node at a particular horizontal distance.
  • As you reach a node , simply update its vertical distance key value in the map with the data of this current node.
  • Only the last nodes of each vertical line will remain in the map while all other previous nodes will get overwritten.
  • Print the values in the map.
#3

Sir, my code is still not working. As far as I have observed is that my code is unable to form binary tree from level traversal inputs like 1 -1 2 -1 3 -1 -1 though it has worked for many such inputs. But when it comes to skewed trees, it fails. I think I will be able to solve this question if you tell me the correct method to make binary tree from level order inputs.

import java.util.*;
import java.util.Map.Entry;
public class Main
{
class Node
{
int data; //data of the node
int hd; //horizontal distance of the node
Node left, right; //left and right references
public Node(int key)
{
data = key;
hd = Integer.MAX_VALUE;
left = right = null;
}
}
Node root;
public Node insertLevelOrder(ArrayList arr, Node root,int i,int path)
{
if (i < arr.size())
{
Node temp = new Node(arr.get(i));
if(temp.data==(-1))
{
root=null;
return root;
}
else
root = temp;
root.left = insertLevelOrder(arr, root.left,2 * i + 1,path-1);
root.right = insertLevelOrder(arr, root.right, 2 * i + 2,path+1);
}
return root;
}
public void bottomView()
{
if (root == null)
return;
int hd = 0;
Map<Integer, Integer> map = new TreeMap<>();
Queue queue = new LinkedList();
root.hd = hd;
queue.add(root);
while (!queue.isEmpty())
{
Node temp = queue.remove();
hd = temp.hd;
if(temp.data!=-1)
map.put(hd, temp.data);
if (temp.left != null)
{
temp.left.hd = hd-1;
queue.add(temp.left);
}
if (temp.right != null)
{
temp.right.hd = hd+1;
queue.add(temp.right);
}
}
Set<Entry<Integer, Integer>> set = map.entrySet();
Iterator<Entry<Integer, Integer>> iterator = set.iterator();
while (iterator.hasNext())
{
Map.Entry<Integer, Integer> me = iterator.next();
System.out.print(me.getValue()+" ");
}
}

public void display(Node node)
{
    String str="";
    if(node.left!=null)
        str=str+node.left.data+"=>";
    else
        str=str+"END=>";
    str=str+node.data;
    if(node.right!=null)
        str=str+"<=" + node.right.data;
    else
        str=str+"<=END";
    System.out.println(str);
    if(node.left!=null)
            this.display(node.left);
    if(node.right!=null)
            this.display(node.right);
}

public static void main(String args[]) throws Exception
{ 
    Main tree = new Main(); 
    Scanner sc=new Scanner(System.in);
    
    ArrayList<Integer> list=new ArrayList<>();
    int node=0,nnode=0;
    while(nnode!=(node+1))
    {
        int n=sc.nextInt();
        if(n==-1)
        {
            list.add(n);
            nnode++;
        }
        else
        {
            list.add(n);
            node++;
        }
    }
    tree.root=tree.insertLevelOrder(list,tree.root,0,0);
    tree.bottomView();
    
}

}

#4

Sorry sir, I found my mistake.

1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.