Java Program to Check if a Binary Tree is Subtree of Another Binary Tree

«
»
This Java program is to Implement binary tree and check whether a tree is subtree of another. This can be done in two ways. A tree can be subtree of another if they have same structure (same object references but different value) and with same structure and values. This given class checks for both.

Here is the source code of the Java Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to check whether a binary tree is subtree of another tree
  2. class Btrees
  3. {
  4.     Object value;
  5.     Btrees Left;
  6.     Btrees Right;
  7.  
  8.     Btrees(int k)
  9.     {
  10.         value = k;
  11.     }
  12. }
  13.  
  14. public class SubBinaryTree
  15. {
  16.     public static boolean ifsubtreeRef(Btrees t1, Btrees t2)
  17.     {
  18.         if (t2 == null)
  19.             return true;
  20.         if (t1 == null)
  21.             return false;
  22.         return (t1 == t2) || ifsubtreeRef(t1.Left, t2)
  23.                 || ifsubtreeRef(t1.Right, t2);
  24.     }
  25.  
  26.     public static boolean ifsubtreeValue(Btrees t1, Btrees t2)
  27.     {
  28.         if (t2 == null)
  29.             return true;
  30.         if (t1 == null)
  31.             return false;
  32.         if (t1.value == t2.value)
  33.             if (ifsubtreeValue(t1.Left, t2.Left)
  34.                     && ifsubtreeValue(t1.Right, t2.Right))
  35.                 return true;
  36.         return ifsubtreeValue(t1.Left, t2) || ifsubtreeValue(t1.Right, t2);
  37.     }
  38.  
  39.     public static void main(String[] args)
  40.     {
  41.         Btrees t1 = new Btrees(1);
  42.         t1.Left = new Btrees(2);
  43.         t1.Right = new Btrees(3);
  44.         t1.Right.Left = new Btrees(4);
  45.         t1.Right.Right = new Btrees(5);
  46.  
  47.         Btrees t2 = new Btrees(3);
  48.         t2.Left = new Btrees(4);
  49.         t2.Right = new Btrees(5);
  50.  
  51.         if (ifsubtreeRef(t1, t2))
  52.             System.out.println("T2 is sub-tree of T1 (Reference wise)");
  53.         else
  54.             System.out.println("T2 is NOT sub-tree of T1 (Reference wise)");
  55.  
  56.         if (ifsubtreeValue(t1, t2))
  57.             System.out.println("T2 is sub-tree of T1 (Value wise)");
  58.         else
  59.             System.out.println("T2 is NOT sub-tree of T1 (Value wise)");
  60.     }
  61. }

Output:

advertisement
$ javac SubBinaryTree.java
$ java SubBinaryTree
 
T2 is NOT sub-tree of T1 (Reference wise)
T2 is sub-tree of T1 (Value wise)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.