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

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS