i didn’t understood the question properly. What is meant by “STRUCTURAL IDENTITY” here? I assumed that the given trees are equally balanced / unbalanced. So, I calculated the difference of the difference of the left and right subtrees of the 2 given trees.
CODE:
import java.util.;
import java.lang.;
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) {
int hls_t = this.height(tnode.left);
int hrs_t = this.height(tnode.right);
int heightDifference_t = Math.abs(hls_t - hrs_t);
int hls_o = this.height(onode.left);
int hrs_o = this.height(onode.right);
int heightDifference_o = Math.abs(hls_o - hrs_o);
if(Math.abs(heightDifference_o - heightDifference_t) == 0) {
return true;
}
else {
return false;
}
}
private int height(Node node) {
if(node == null) {
return -1;
}
int lheight = this.height(node.left);
int rheight = this.height(node.right);
int height = Math.max(lheight, rheight);
return height + 1;
}
}
}