Check If a Tree is Subtree of Another Tree

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

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

The below code is a C# function that checks if a binary tree is a subtree of another binary tree. It uses two helper functions: IsSubtree and CheckSubtree.

TreeNode represents a tree node.

class TreeNode {

  public int val;
  public TreeNode left, right;
  public TreeNode(int x) {
    val = x;
    left = null;
    right = null;
  }

}

IsSubtree takes two parameters: root and subRoot, which are the root nodes of the two trees. It returns true if subRoot is a subtree of root and false otherwise.

public bool IsSubtree(TreeNode root, TreeNode subRoot) {

  if (root == null) {
    return false;
  }

  if (CheckSubtree(root, subRoot))
    return true;

  return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);

}

• Checking if the root is null. If so, it means there is no tree to search, so it returns false.
• Calling CheckSubtree with root and subRoot as arguments. This function will compare the two trees and return true if they are identical and false otherwise.
• If CheckSubtree returns true, it means subRoot is a subtree of the root, so IsSubtree returns true as well.
• If CheckSubtree returns false, it means subRoot is not a subtree of root at the current node, so it recursively calls itself with root.left and subRoot, and root.right and subRoot, as arguments. This will check if the subRoot is a subtree of any of the left or right subtrees of the root.
• It returns the logical OR of the two recursive calls, which will be true if either one of them is true and false if both are false.

CheckSubtree takes two parameters: root and subRoot, which are the root nodes of the two trees. It returns true if the two trees are identical and false otherwise.

bool CheckSubtree(TreeNode root, TreeNode subRoot) {

  if (root == null && subRoot == null)
    return true;
  if (root == null || subRoot == null)
    return false;

  if (root.val != subRoot.val) return false;

  return CheckSubtree(root.left, subRoot.left) && CheckSubtree(root.right, subRoot.right);

}

• Checking if both root and subRoot are null. If so, it means both trees are empty, so they are identical, and it returns true.
• Checking if either root or subRoot is null. If so, it means one tree is empty, and the other is not, so they are not identical, and it returns false.
• Checking if the values of root and subRoot are equal. If not, it means the nodes are different, so the trees are not identical, and it returns false.
• Recursively calling itself with root.left and subRoot.left, and root.right and subRoot.right, as arguments. This will compare the left and right subtrees of the two trees.
• Returning the logical AND of the two recursive calls, which will be true if both of them are true, and false if either one of them is false.

Sure, I’ll try to explain with an example. Suppose we have the following binary trees.

Root

SubRoot

The subRoot tree is a subtree of the root tree because it is identical to the left subtree of the root tree. To find this, the code does the following steps.

• It checks if the root (3) is null. It is not, so it proceeds to the next step.
• It calls CheckSubtree with root (3) and subRoot (4) as arguments. This function will compare the two trees and return true if they are identical and false otherwise.

To find the result of CheckSubtree, it repeats the same steps as below.

• It checks if both root (3) and subRoot (4) are null. They are not, so it proceeds to the next step.
• It checks if either root (3) or subRoot (4) is null. They are not, so it proceeds to the next step.
• It checks if the values of root (3) and subRoot (4) are equal. They are not, so it returns false.

Since CheckSubtree returns false, it means subRoot is not a subtree of root at the current node, so it recursively calls itself with root.left (4) and subRoot (4), and root.right (5) and subRoot (4) as arguments. This will check if the subRoot is a subtree of any of the left or right subtrees of the root.

• It returns the logical OR of the two recursive calls, which will be true if either one of them is true and false if both are false. This is the final return value.

To find the result of the left recursive call, it repeats the same steps as above:

• It checks if the root.left (4) is null. It is not, so it proceeds to the next step.
• It calls CheckSubtree with root.left (4) and subRoot (4) as arguments. This function will compare the two trees and return true if they are identical and false otherwise.

To find the result of CheckSubtree, it repeats the same steps as below:

• It checks if both root.left (4) and subRoot (4) are null. They are not, so it proceeds to the next step.
• It checks if either root.left (4) or subRoot (4) is null. They are not, so it proceeds to the next step.
• It checks the values of root.left (4) and subRoot (4) are equal. They are, so it proceeds to the next step.
• It recursively calls itself with root.left.left (1) and subRoot.left (1), and root.left.right (2) and subRoot.right (2), as arguments. This will compare the left and right subtrees of the two trees.
• It returns the logical AND of the two recursive calls, which will be true if both of them are true, and false if either one of them is false. This is the return value for this subtree.

To find the result of the left recursive call, it repeats the same steps as below:

• It checks if both root.left.left (1) and subRoot.left (1) are null. They are not, so it proceeds to the next step.
• It checks if either root.left.left (1) or subRoot.left (1) is null. They are not, so it proceeds to the next step.
• It checks if the values of root.left.left (1) and subRoot.left (1) are equal. They are, so it returns true.

To find the result of the right recursive call, it repeats the same steps as below:

• It checks if both root.left.right (2) and subRoot.right (2) are null. They are not, so it proceeds to the next step.
• It checks if either root.left.right (2) or subRoot.right (2) is null. They are not, so it proceeds to the next step.
• It checks if the values of root.left.right (2) and subRoot.right (2) are equal. They are, so it returns true.

The logical AND of the two results for this subtree is true, so this is the return value for this subtree.

Since CheckSubtree returns true, it means subRoot is a subtree of root at this node, so this recursive call returns true as well.

To find the result of the right recursive call, it repeats the same steps as above:

• It checks if the root.right (5) is null. It is not, so it proceeds to the next step.
• It calls CheckSubtree with root.right (5) and subRoot (4) as arguments. This function will compare the two trees and return true if they are identical and false otherwise.

To find the result of CheckSubtree, it repeats the same steps as below:

• It checks if both root.right (5) and subRoot (4) are null. They are not, so it proceeds to the next step.
• It checks if either root.right (5) or subRoot (4) is null. They are not, so it proceeds to the next step.
• It checks if the values of root.right (5) and subRoot (4) are equal. They are not, so it returns false.

Since CheckSubtree returns false, it means subRoot is not a subtree of root at this node, so this recursive call returns false as well.

The logical OR of the two results for the whole tree is true because the left recursive call returned true, so this is the final return value.

The time complexity of the code is O(m*n), where m and n are the number of nodes in the two trees. This is because, in the worst case, we have to compare every node in the subRoot tree with every node in the root tree, which takes O(m*n) time. A possible way to optimize the code is to use a hashing technique to compare the trees in O(m+n) time, but this would require extra space.