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:
- Traverse
the main tree T1 to find nodes that match the root of T2.
- 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
- TreeNode
Class:
- Defines
the structure of a node in the binary tree with a value, and pointers to
the left and right children.
- 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.
- 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.
- 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
- Save
the TreeNode and SubtreeCheck classes.
- Compile
the code:
sh
javac
SubtreeCheck.java |
- 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.
0 Comments