From Passion to Profession
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Data Structure - Whether a Small tree is a Sub-tree of a Large Tree?

10/13/2013

0 Comments

 
Picture
In this post, I note the approach and my thought process about determining whether a given smaller tree (t2) is a sub-tree of another larger tree (t1).

First, the approach: Since I know t2 is smaller and it is to be matched/found in a larger tree t1, I'll take the approach of scanning through the larger tree t1, and t1's children, by trying to find a match of t2 in t1's left child tree and find a match of t2 in t1's right child tree, recursively.

Thought Process

1. Define the contract of the function for finding sub-tree
boolean subTree(TreeNode t1, TreeNode t2)
2. Consider boundary conditions for finding sub-tree

Consider what if the small tree t2 is null, and what if the bigger tree t1 is null.

3. Put in core logic as mentioned in the above 'approach' section for finding a match so I can say a sub-tree is found.

If t1.data is the same as t2.data, further check if they are the exactly match. However, if t1.data is not the same as t2.data, check if t2 is a sub-tree of t1.left or a sub-tree of t2.left.

4. Implement the logic for checking if 2 trees are exactly the same.

Code Sample

boolean subTree(TreeNode t1, TreeNode t2) {
  if (t2 == null)
    return true;  // boundary condition: the empty tree is always a subtree
  if (t1 == null)
    return false; // boundary condition: big tree empty & subtree still not found.

  if (t1.data == t2.data) {
    if (matchTree(t1,t2))
      return true;
  }
  else{
    return (subTree(t1.left, t2) || subTree(t1.right, t2));
  }
}

// An auxiliary function to determine whether 2 trees are exact match
boolean matchTree(TreeNode t1, TreeNode t2) {
  if (t2 == null && t1 == null)
    return true;  // boundary condition
  if (t1 == null || t2 == null)
    return false; // boundary condition

  if (t1.data != t2.data){
    return false; // data doesn’t match
  }
  else{
    return (matchTree(t1.left, t2.left) && matchTree(t1.right, t2.right));
  }
}

0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar