From fe29ea0188a76b73d6c99c208d7dc4addb9da76d Mon Sep 17 00:00:00 2001 From: Michael Hunteman Date: Fri, 7 Oct 2022 17:13:40 -0500 Subject: Add Subtree --- Subtree.java | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 Subtree.java diff --git a/Subtree.java b/Subtree.java new file mode 100644 index 0000000..119c1a1 --- /dev/null +++ b/Subtree.java @@ -0,0 +1,28 @@ +import java.lang.*; +import java.util.*; +import node.*; + +class Subtree { + public static boolean isSubtree(TreeNode root, TreeNode subRoot) { + if (root == null && subRoot == null) + return true; + else if (root == null || subRoot == null) + return false; + else if (root.val == subRoot.val) + return isSubtree(root.left, subRoot.left) + && isSubtree(root.right, subRoot.right); + return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); + } + + public static void main(String[] args) { + TreeNode leftLeaf = new TreeNode(1); + TreeNode middleLeaf = new TreeNode(2); + TreeNode leftParent = new TreeNode(4, leftLeaf, middleLeaf); + TreeNode rightLeaf = new TreeNode(5); + TreeNode root = new TreeNode(3, leftParent, rightLeaf); + TreeNode subLeft = new TreeNode(1); + TreeNode subRight = new TreeNode(2); + TreeNode subRoot = new TreeNode(4, subLeft, subRight); + System.out.println(isSubtree(root, subRoot)); + } +} -- cgit v1.2.3