Trusted answers to developer questions

Ravi

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:

- The root node of
`X`

and`Y`

have the same data or the roots are pointing to`null`

. - The left subtree of
`X`

is identical to the left subtree of`Y`

. - The right subtree of
`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"); } }

- Lines 3 to 11: We define a
`Node`

class that consists of`data`

,`left`

node, and`right`

node. - Line 13: We declare the root of tree
`X`

is`xroot`

and the root of tree`Y`

is`yroot`

. - Lines 15 to 26: We define the
`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`

. - Lines 31 to 40: We construct tree
`X`

and tree`Y`

. - Line 42: We invoke the
`areTreesIdentical()`

method with the roots of`X`

and`Y`

.

RELATED TAGS

binary tree

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses