Subtree of Another Tree

Lets say we have this problem:

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.

This is classified as an easy problem from LeetCode, and we find that it actually is quite simple after we take the time to understand it.

I find the easiest step to understanding anything is to first visualize it.

Tree and Subtree

Here, we see on the right we have a full subtree consisting of nodes 3, 1, 6, & 7 which are equivalent to the part of the tree on the left beginning at node 3.

TreeNode

First, we should define the TreeNode. This is already done for us in LeetCode, but lets explain it briefly as well.

In this case, we are dealing with a binary tree node, which is a specific type of tree data structure in which each node has at most two children, commonly referred to as the left child and the right child. Each child node can, in turn, have its own two children, forming a hierarchical structure like we see in the image above.

The class is defined as follows:

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode() {}

  TreeNode(int val) { this.val = val; }

  TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}

Determining Matching Subtrees

We know that we can traverse a binary tree by moving to the left or to the right.

With two binary trees, we can traverse them at the same time, comparing values at each step.

Lets take a look at the solution first, and then we will take the time to understand it.

public Boolean isSubtree(TreeNode root, TreeNode subRoot) {

    // No subtree has been found
    if(root == null) return false;

    // Check current subtree
    if(root.val == subRoot.val) {
        if(checkTree(root, subRoot) == true) return true;
    }

    // Check if either left or right of tree has a matching val to subtree root
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

public Boolean checkTree(TreeNode root, TreeNode subRoot) {
    if(root == null && subRoot == null) return true; // Reached the end
    if(root == null || subRoot == null) return false; // Reached the end and there is a mismatch

    if(root.val == subRoot.val) { // There is a match. Compare rest of subtrees
        return checkTree(root.left, subRoot.left) && checkTree(root.right, subRoot.right);
    }

    return false;
}

What are we trying to do in isSubtree() ?

First, we want to make sure the root is not null, because if we get here, it means we have not found a subtree after the next steps of this function, which recursively calls itself with its children until we meet the conditions to begin looking for a subtree.

Which brings us to the point: we are traversing down the tree, attempting to find a node in the tree that matches the root of the subtree.

These are the current roots of the trees:

• Left (yellow) is the main tree
• Right (green) is the subtree

We check if root.val == subRoot.val and we get false since 8 != 3 and then we recursively call isSubtree(root.left, subRoot) to the left of 8.

8.left = 3

On our initial tree, to the left of 8 was the node 3. So now we have a match! root.val == subRoot.val . 3 == 3

We need to check for an exact match between the trees

Now that we found a node match in the original tree and the subtree, we have to traverse both of these trees in the checkTree() function and make sure we have an exact match while traversing.

public static Boolean checkTree(TreeNode root, TreeNode subRoot) {
    if(root == null && subRoot == null) return true; // Reached the end
    if(root == null || subRoot == null) return false; // Reached the end and there is a mismatch

    if(root.val == subRoot.val) { // There is a match. Compare rest of subtrees
        return checkTree(root.left, subRoot.left) && checkTree(root.right, subRoot.right);
    }

    return false;
}

checkTree() will return false under two conditions:

• Either root or subRoot node is null
• root.val does not equal subRoot.val

If the root or the subRoot is null, it means one exists and the other does not. This would indicate the trees are inequivalent.

If the comparing tree nodes do not have the same value, it would similarly indicate the trees are inequivalent.

But first

checkTree() sees if both the root and the subRoot are null. If they both are, we will have recursively traversed this to where both root & subRoot are null. This only means, so far (up to that point) they are both still equivalent. A good example of this is at node 1. We traverse left of that and see that both root and subRoot are null. It doesn’t mean the entire tree is equivalent, it just means up to that point it is.

We still have to recursively call checkTree() on both the left side of root and subRoot and the right side of root and subRoot.

Only if both these sides return true on each recursive call will checkTree() return true to isSubtree() .

Lets imagine checkTree on the call stack (beginning at root & subRoot = 3).

As root.val == subRoot.val, we traverse down the left side of the tree. When we reach node 1, we check the left.

• root.val == null
• subRoot.val == null

We return true and pop it off the stack.

Then, we go to the right.

• root.val == null
• subRoot.val == null

Here is what it would look like on the call stack (first going left and then right).

checkTree(null,null) // Left -> return true and pop off stack
checkTree(1,1) 
checkTree(3,3)

checkTree(null,null) // Right -> return true and pop off stack
checkTree(1,1)
checkTree(3,3)

Now, since we have recursively checked both left & right for node 1, we know that it will return true.

checkTree(1,1) // Return true and pop off stack
checkTree(3,3)

We now only have checkTree(3,3) on the call stack.

checkTree(3,3)

We have traversed down its left side and got returned true, but now we have to go down its right side and get true as well because of the requirement (&&):

checkTree(root.left, subRoot.left) && checkTree(root.right, subRoot.right)

So, we go down the right side, first to node 6, and then after, to the left, where we get null.

checkTree(null,null) // Return true and pop off
checkTree(6,6)
checkTree(3,3)

So now node 6 on the left side is true, we have to go to the right, to 7 and then to the left and right (which are both null)

checkTree(null, null) // Left side -> return true and pop off
checkTree(7,7)
checkTree(6,6)
checkTree(3,3)

checkTree(null, null) // Right side -> return true and pop off
checkTree(7,7)
checkTree(6,6)
checkTree(3,3)

Now 7 has two trues (left and right), so it will return true to 6

checkTree(7,7) // Return true and pop off
checkTree(6,6)
checkTree(3,3)

Remember, 6 on the left side was already found to be true, so now on the right side we are also returning true from 7.

checkTree(6,6) // Return true and pop off
checkTree(3,3)

Lastly, 6 will return true on the right side to 3, and we already found the left side to be true, so the same thing will happen (checkTree(3,3) will return true).

 checkTree(3,3) // Return true and pop off

Returning the result to the main function

The function checkTree(3,3)is returned to isSubtree() as true. When checkTree() is returned to isSubtree(), we have to remember that isSubtree() is a also a recursive function.

It differs from checkTree(), however in its primary goal. Where checkTree() requests true results from both its left and right subtrees, isSubtree() only requires one of the children to find a subtree that has a perfect match.

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

If we take a look one more time, to the right of 8 sits the node 10. If we remember the part of isSubtree() where we have: if(root == null) return false, we can imagine the call stack beginning at root = 8 and subRoot = 3.

Left:

isSubtree(3,3) // Return true and pop off (call to checkTree)
isSubtree(8,3)

Right (two sides, left & right of node 10)

checkTree(null, 3) // Left -> Return false and pop off stack
isSubtree(10,3) 
isSubtree(8,3)

checkTree(null, 3) // Right -> Return false and pop off stack
isSubtree(10,3) 
isSubtree(8,3)

Now, since neither the left nor the right of isSubtree(10,3) returned true, we have to have itself return false and pop off the stack.

isSubtree(10,3) // Return false and pop off stack
isSubtree(8,3)

Finally, isSubtree(8,3) returned true from the left, which was isSubtree(3,3) and false from the right, which was isSubtree(10,3). Since we only need one of them to be true:

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

isSubtree() ultimately returns true.

Once again, our solution looks like:

public Boolean isSubtree(TreeNode root, TreeNode subRoot) {

    // No subtree has been found
    if(root == null) return false;

    // Check current subtree
    if(root.val == subRoot.val) {
        if(checkTree(root, subRoot) == true) return true;
    }

    // Check if either left or right of tree has a matching val to subtree root
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

public Boolean checkTree(TreeNode root, TreeNode subRoot) {
    if(root == null && subRoot == null) return true; // Reached the end
    if(root == null || subRoot == null) return false; // Reached the end and there is a mismatch

    if(root.val == subRoot.val) { // There is a match. Compare rest of subtrees
        return checkTree(root.left, subRoot.left) && checkTree(root.right, subRoot.right);
    }

    return false;
}