Sub tree from a tree

To determine if a tree T2 is a subtree of another tree T1, you can use a recursive approach in Java. This problem can be broken down into two main tasks:

1. Traverse the main tree T1 to find nodes that match the root of T2.
2. For each such node, check if the subtree starting at that node is identical to T2.

Here's a step-by-step guide and corresponding Java code to achieve this:

Step 1: Define the Tree Node

First, create a class to represent nodes of the tree.

java

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

 

Step 2: Implement the Subtree Check

Implement the logic to check if one tree is a subtree of another tree.

SubtreeCheck.java:

java

public class SubtreeCheck {         // Method to check if T2 is a subtree of T1     public boolean isSubtree(TreeNode T1, TreeNode T2) {         if (T2 == null) return true; // An empty tree is a subtree of any tree         if (T1 == null) return false; // Non-empty T2 cannot be a subtree of an empty T1           if (areIdentical(T1, T2)) return true;           return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);     }       // Method to check if two trees are identical     private boolean areIdentical(TreeNode root1, TreeNode root2) {         if (root1 == null && root2 == null) return true;         if (root1 == null || root2 == null) return false;           return (root1.val == root2.val                 && areIdentical(root1.left, root2.left)                 && areIdentical(root1.right, root2.right));     }       public static void main(String[] args) {         SubtreeCheck subtreeCheck = new SubtreeCheck();           // Create Tree T1         TreeNode T1 = new TreeNode(1);         T1.left = new TreeNode(2);         T1.right = new TreeNode(3);         T1.left.left = new TreeNode(4);         T1.left.right = new TreeNode(5);         T1.right.left = new TreeNode(6);         T1.right.right = new TreeNode(7);           // Create Tree T2         TreeNode T2 = new TreeNode(3);         T2.left = new TreeNode(6);         T2.right = new TreeNode(7);           // Check if T2 is a subtree of T1         boolean result = subtreeCheck.isSubtree(T1, T2);         System.out.println("T2 is a subtree of T1: " + result);     } }

 

Explanation

1. TreeNode Class:
• Defines the structure of a node in the binary tree with a value, and pointers to the left and right children.
2. isSubtree Method:
• Checks if T2 is a subtree of T1.
• If T2 is null, it is considered a subtree of any tree.
• If T1 is null, T2 (non-null) cannot be a subtree.
• Checks if the current nodes of T1 and T2 are identical using areIdentical.
• Recursively checks the left and right subtrees of T1.
3. areIdentical Method:
• Checks if two trees are identical by comparing their values and recursively checking their left and right subtrees.
• If both nodes are null, they are considered identical.
• If one is null and the other is not, they are not identical.
• Checks if the values of the nodes are equal and if their left and right subtrees are identical.
4. main Method:
• Creates two trees, T1 and T2.
• Calls the isSubtree method to check if T2 is a subtree of T1.
• Prints the result.

Running the Code

1. Save the TreeNode and SubtreeCheck classes.
2. Compile the code:

sh

javac SubtreeCheck.java

3. Run the code:

sh

SubtreeCheck.java

 

This should print T2 is a subtree of T1: true if T2 is indeed a subtree of T1. You can modify the trees in the main method to test different cases.