Given the roots of two binary trees, determine whether or not two binary trees are identical. Identical trees have the same structure and information at every node.
Check the following slides for examples:
Let’s name the two trees X
and Y
.
The solution is to use depth first search traversal. We can recursively solve this problem.
The base case is when both or either one of the nodes of the two trees is null
.
We can say X
and Y
are identical when the following conditions are satisfied:
X
and Y
have the same data or the roots are pointing to null
.X
is identical to the left subtree of Y
.X
is identical to the right subtree of Y
.Let’s look at the code below:
class Main{static class Node {int data;Node left, right;Node(int item) {data = item;left = right = null;}}private Node xroot, yroot;boolean areTreesIdentical(Node xroot, Node yroot) {if (xroot == null && yroot == null) return true;if (xroot != null && yroot != null) {return ((xroot.data == yroot.data) &&areTreesIdentical(xroot.left, yroot.left) &&areTreesIdentical(xroot.right, yroot.right));}return false;}public static void main(String[] args) {Main main = new Main();main.xroot = new Node(1);main.xroot.left = new Node(2);main.xroot.right = new Node(3);main.xroot.left.left = new Node(2);main.xroot.left.right = new Node(2);main.yroot = new Node(1);main.yroot.left = new Node(2);main.yroot.right = new Node(3);main.yroot.left.left = new Node(2);System.out.println(main.areTreesIdentical(main.xroot, main.yroot)?"Trees are identical": "Trees are not identical");}}
Node
class that consists of data
, left
node, and right
node.X
is xroot
and the root of tree Y
is yroot
.areTreesIdentical
method that accepts the roots of the two trees as arguments. We check whether the current node data is equal and then recursively check for the left and right subtrees of X
and Y
.X
and tree Y
.areTreesIdentical()
method with the roots of X
and Y
.