criskgl
11/1/2019 - 1:30 PM

Check if tree is subtree of bigger tree

Subtree of a Tree

Explanation

Do a Preorder traversal of both trees saving the road the go through ** as a string ** Compare if the smaller string is contained in the bigger one. If so its a subtree

Things to note

  • We also add to the string when the L or R nodes are null
  • We add to string a #centinel value
isSubtree.java
content_copyfile_download
class Solution {
  public boolean isSubtree(TreeNode s, TreeNode t) {
      StringBuilder fp = new StringBuilder();
      StringBuilder fp2 = new StringBuilder();
      return (getFootPrint(s, fp).contains(getFootPrint(t, fp2))) ? true : false;
  }
  public String getFootPrint(TreeNode t, StringBuilder footPrint){
      footPrint.append(("#"+t.val));
      if(t.left != null) getFootPrint(t.left, footPrint);
      else footPrint.append("XL");
      if(t.right != null) getFootPrint(t.right, footPrint);
      else footPrint.append("XR");
      return footPrint.toString();
  }
}