Structurally identical(binary Tree)

#1

import java.util.*;
public class Main {

static Scanner scn = new Scanner(System.in);

public static void main(String[] args) {
	Main m = new Main();
	BinaryTree bt1 = m.new BinaryTree();
	BinaryTree bt2 = m.new BinaryTree();
	System.out.println(bt1.structurallyIdentical(bt2));
}

private class BinaryTree {
	private class Node {
		int data;
		Node left;
		Node right;
	}

	private Node root;
	private int size;

	public BinaryTree() {
		this.root = this.takeInput(null, false);
	}

	public Node takeInput(Node parent, boolean ilc) {

		int cdata = scn.nextInt();
		Node child = new Node();
		child.data = cdata;
		this.size++;

		// left
		boolean hlc = scn.nextBoolean();

		if (hlc) {
			child.left = this.takeInput(child, true);
		}

		// right
		boolean hrc = scn.nextBoolean();

		if (hrc) {
			child.right = this.takeInput(child, false);
		}

		// return
		return child;
	}

	public boolean structurallyIdentical(BinaryTree other) {
		return this.structurallyIdentical(this.root, other.root);
	}

	private boolean structurallyIdentical(Node tnode, Node onode) {
		
    LinkedList<Node> queue=new LinkedList<>();
    int arr[]=new int[1000];
	int arr1[]=new int[1000];
	int i=0,j=0;
    queue.add(tnode);
   
     LinkedList<Node> queue1=new LinkedList<>();
	  queue1.add(onode);

	while(!queue.isEmpty())
	   {
		 Node rv=queue.removeFirst();
		 System.out.println(rv);

		 if(rv.left!=null)
		   { queue.addLast(rv.left);
		      arr[i]=arr[i]+1;}

		  if(rv.right!=null)
		   { queue.addLast(rv.right);
               arr[i]=arr[i]+1;
		   }
            i++;
	   }
      

	  while(!queue1.isEmpty())
	   {
		 Node rv=queue1.removeFirst();
		 System.out.println(rv);

		 if(rv.left!=null)
		   { queue1.addLast(rv.left);
		      arr1[j]=arr1[j]+1;}

		  if(rv.right!=null)
		   {    queue1.addLast(rv.right);
               arr1[j]=arr1[j]+1;
		   }
            j++;
	   }
	
	 if(i!=j)
	   return false;

	  else
	   {  int k;
         for( k=0;k<i;k++)
            {
				if(arr[k]!=arr1[k])
				  break;
			}
	      if(k>=i)
	       return true;

		  else
           return false;
	   }


	}

}

}

why it gives wrong answer ? when i submit when i run provide test cases then it give correct answer

#2

hi @abhishekg
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

you code willl not work for this testcase-

   A         and      C   
  /                    \
B                        D

you array will store same values but they are structurally different.

#4

@abhishekg
please mark your doubt as resolved and rate me as well.