Error in "Structurally Identical (Binary Tree)" problem

#1

THE CODE BELOW IS GIVING CORRECT OUTPUTS IN NETBEANS. BUT IN IDE OF CB, IT IS SHOWING ERROR, THAT IS, “NO SUCH ELEMENT EXCEPTION” DURING COMPILATION. THE CODE IS RUNNING FOR THE FIRST TREE BUT SHOWING EXCEPTION FOR SECOND TREE. PLEASE CHECK WHAT IS THE PROBLEM.

import java.util.*;
public class Main
{
private class Node
{
int data;
Node left;
Node right;
Node(int data,Node left,Node right)
{
this.data=data;
this.left=left;
this.right=right;
}
}
Node root=null;
int size=0;

Main()
{
    Scanner s=new Scanner(System.in);
    this.root=takeInput(s,null,false);	//
}

public Node takeInput(Scanner s,Node parent,boolean isLeftOrRight)
{
    int nodeData=s.nextInt();		//
    Node node=new Node(nodeData,null,null);
    this.size++;
    
    boolean choice=false;
    choice=s.nextBoolean();
    if(choice)
        node.left=takeInput(s,node,true);
    
    choice=false;
    choice=s.nextBoolean();
    if(choice)
        node.right=takeInput(s,node,false);
    return node;
}

public ArrayList<Boolean> display(Node node,ArrayList<Boolean> list)
{
    String str="";
    if(node.left!=null)
    {
        str=str+node.left.data+"=>";
        list.add(true);
    }
    else
    {
        str=str+"END=>";
        list.add(false);
    }
    str=str+node.data;
    if(node.right!=null)
    {
        str=str+"<=" + node.right.data;
        list.add(true);
    }
    else
    {
        str=str+"<=END";
        list.add(false);
    }
    if(node.left!=null)
            this.display(node.left,list);
    if(node.right!=null)
            this.display(node.right,list);
    return list;
}

public boolean check(ArrayList<Boolean> list1,ArrayList<Boolean> list2)
{
    for(int i=0;i<list1.size();i++)
    {
        if(list1.get(i)!=list2.get(i))
            return false;
    }
    return true;
}

public static void main(String[] args) 
{
    Main tree1=new Main();
    ArrayList<Boolean> ans1=tree1.display(tree1.root,new ArrayList<>());
    Main tree2=new Main();
    ArrayList<Boolean> ans2=tree2.display(tree2.root,new ArrayList<>());
    if(ans1.size()!=ans2.size())
        System.out.println(false);
    else
        System.out.println(tree1.check(ans1,ans2));
}

}

#2

@vinay86048,

You don’t have to compare data in the nodes as mentioned in the question : They may or may not have the same data though.

Suggested Approach:

  • Here the smaller problem is to find out whether the left subtree and right subtree of the root node for the two trees are structurally similar or not.
  • If true, return true. Else even if one the condition is false, return false.
  • There will be two base cases for the given question.
    a) If both the trees are empty, return true.
    b) If one of the trees remain null and other one does not, then return false.
#3

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.

#4

Sir, the code was giving Exception at the time compilation only in CB ide. But on netbeans, it gave correct output. Now, I have used your logic but still it is working on netbeans but reporting same exception on CB ide.
Here is the modified code.

import java.util.*;
public class Main
{
private class Node
{
int data;
Node left;
Node right;
Node(int data,Node left,Node right)
{
this.data=data;
this.left=left;
this.right=right;
}
}
Node root=null;
int size=0;

Main()
{
    Scanner s=new Scanner(System.in);
    this.root=takeInput(s,null,false);
}

public Node takeInput(Scanner s,Node parent,boolean isLeftOrRight)
{
    
    int nodeData=s.nextInt();
    Node node=new Node(nodeData,null,null);
    this.size++;
    
    boolean choice=false;
    choice=s.nextBoolean();
    if(choice)
        node.left=takeInput(s,node,true);
    
    choice=false;
    choice=s.nextBoolean();
    if(choice)
        node.right=takeInput(s,node,false);
    return node;
}
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";
    }
    if(node.left!=null)
            this.display(node.left);
    if(node.right!=null)
            this.display(node.right);
}

public boolean check(Node node1,Node node2)
{
    if(node1==null&&node2==null)
        return true;
    if((node1!=null&&node2==null)||(node2!=null&&node1==null))
        return false;
    boolean a1=check(node1.left,node2.left);
    boolean a2=check(node1.right,node2.right);
    return a1&a2;
}

public static void main(String[] args) 
{
    Main tree1=new Main();
    Main tree2=new Main();
    System.out.println(tree1.check(tree1.root,tree2.root));
}

}

#5

Identical
Identical824Ă—293 5.77 KB

#6

@vinay86048,
Keep scanner as public instead of declaring a new scanner object for every Main object. This is causing input error. It will work on the local machine but give error on online IDEs.

https://ide.codingblocks.com/s/234789 corrected code.

Your logic is correct. :slight_smile:

#7

Thank you sir. But what was the problem in declaring scanner in each object? Why it caused input error in online IDE.

#8

@vinay86048,

Might be because we can use only one object for input on the ide. If we have 2 objects open, 1 is closed and 1 is not closed. That might be causing the error. Another solution is declare the object in the default main method and pass it as a default arg to the Tree obj.