## Tuesday, May 17, 2022

### Easy_Question14 :Check if a binary tree is subtree of another binary tree

Given the roots of two binary trees root and subRoot, return true .

If there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

`Input: root = [3,4,5,1,2], subRoot = [4,1,2]Output: true`

Example 2:

`Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Output: false`

Constraints:

• The number of nodes in the `root` tree is in the range `[1, 2000]`.
• The number of nodes in the `subRoot` tree is in the range `[1, 1000]`.
• `-104 <= root.val <= 104`
• `-104 <= subRoot.val <= 104`

``````class Node {
int data;
Node left, right, nextRight;

Node(int item)
{
data = item;
left = right = nextRight = null;
}
}

public class BinaryTree {
Node root1,root2;

/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
boolean areIdentical(Node root1, Node root2)
{

/* base cases */
if (root1 == null && root2 == null)
return true;

if (root1 == null || root2 == null)
return false;

/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1.data == root2.data
&& areIdentical(root1.left, root2.left)
&& areIdentical(root1.right, root2.right));
}

/* This function returns true if S is a subtree of T, otherwise false */
boolean isSubtree(Node T, Node S)
{
/* base cases */
if (S == null)
return true;

if (T == null)
return false;

/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;

/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T.left, S)
|| isSubtree(T.right, S);
}

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();

// TREE 1
/* Construct the following tree
26
/   \
10     3
/    \     \
4      6      3
\
30  */

tree.root1 = new Node(26);
tree.root1.right = new Node(3);
tree.root1.right.right = new Node(3);
tree.root1.left = new Node(10);
tree.root1.left.left = new Node(4);
tree.root1.left.left.right = new Node(30);
tree.root1.left.right = new Node(6);

// TREE 2
/* Construct the following tree
10
/    \
4      6
\
30  */

tree.root2 = new Node(10);
tree.root2.right = new Node(6);
tree.root2.left = new Node(4);
tree.root2.left.right = new Node(30);

if (tree.isSubtree(tree.root1, tree.root2))
System.out.println("Tree 2 is subtree of Tree 1 ");
else
System.out.println("Tree 2 is not a subtree of Tree 1");
}
}
Time Complexity: Time worst-case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.

Auxiliary space: O(n)

We can solve the above problem in O(n) time``````

## You may also like

a
Kubernetes AWS Java Coding Question
Microservices Core Java Python
Spring Framework AI/MLSpring Boot