Java

/*
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.

 */

public class Subtree_of_Another_Tree {

	public static void main(String[] args) {
		Subtree_of_Another_Tree out = new Subtree_of_Another_Tree();
		Solution s = out.new Solution();

		TreeNode root = new TreeNode(3);
		root.left = new TreeNode(4);
		root.right = new TreeNode(5);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(2);

		TreeNode t = new TreeNode(4);
		t.left = new TreeNode(1);
		t.right = new TreeNode(2);

		System.out.println(s.isSubtree(root, t));
	}


	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */
	public class Solution {
	    public boolean isSubtree(TreeNode s, TreeNode t) {

	        if(s == null && t == null) {
	            return true;
	        }

	        if((s == null && t != null) || (s != null && t == null)) {
	            return false;
	        }

	        // key is to have a same tree check, or else will be skip level same
	        return isSameTree(s, t) || isSubtree(s.left, t) || (isSubtree(s.right, t));
	    }

	    public boolean isSameTree(TreeNode s, TreeNode t) {

	        if(s == null && t == null) {
	            return true;
	        }

	        if((s == null && t != null) || (s != null && t == null)) {
	            return false;
	        }

	    	return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
	    }
	}
}

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null)
            return t == null;
        if (t == null || same(s, t))
            return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean same(TreeNode s, TreeNode t) {
        if (s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        return s.val == t.val && same(s.left, t.left) && same(s.right, t.right);
    }
}

All Problems

All Solutions