w3resource

Java: Test if a binary tree is a subtree of another binary tree

Java Basic: Exercise-150 with Solution

Check Subtree in Binary Tree

Write a Java program to test if a binary tree is a subtree of another binary tree.

Sample Solution:

Java Code:

import java.util.*
public class Solution {
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    public static boolean is_Subtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) return true; // If T2 is null, it's always a subtree (base case)
        if (T1 == null) return false; // If T1 is null but T2 is not, T2 can't be a subtree

        if (is_Same(T1, T2)) return true; // Check if the current subtrees are the same
        if (is_Subtree(T1.left, T2) || is_Subtree(T1.right, T2)) return true; // Check left and right subtrees

        return false; // If none of the above conditions match, T2 is not a subtree of T1
    }

    public static boolean is_Same(TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 == t2; // If one of the nodes is null, both should be null for them to be the same
        } else if (t1.val != t2.val) {
            return false; // If the values are different, the trees are not the same
        } else {
            // Recursively check the left and right subtrees for sameness
            return is_Same(t1.left, t2.left) && is_Same(t1.right, t2.right);
        }
    }

    public static void main(String[] args) {
        // Create two binary trees
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        t1.left  = t2;
        t1.right = t3;

        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        n1.left  = n2;
        n1.right = n3;

        // Check if n1 is a subtree of t1 and print the result
        System.out.println(is_Subtree(t1, n1));
    }
}

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

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

Sample Output:

true

Flowchart:

Flowchart: Java exercises: Test if a binary tree is a subtree of another binary tree.

Java Code Editor:

Previous: Write a Java program to check if a given string is a permutation of another given string.
Next: Write a Java program to find the value of specified expression.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/java-exercises/basic/java-basic-exercise-150.php