Subtree of Another Tree

This question is asked by Amazon. Given two trees s and t, return whether or not t is a subtree of s.

Note: For t to be a subtree of s, not only must each node's value in t match its corresponding node's value in s, but t must also exhibit the exact same structure as s. You may assume both trees s and t exist.

Example(s)

Example 1:

Input:
s =    1
     / \
    3   8
t = 1
     \
      8

Output: false
Explanation:
Tree t has structure: 1 -> 8 (right child)
Tree s has node 1, but its right child is 8, not matching the structure.
Even though values match, the structure is different.

Example 2:

Input:
s =    7
     / \
    8   3
t = 7
   / \
  8   3

Output: true
Explanation:
Tree t matches the structure and values of the root of s.

Example 3:

Input:
s =    7
     / \
    8   3
t = 7
   / \
  8   3
     /
    1

Output: false
Explanation:
Tree t has an extra node (1) that doesn't exist in s.
The structure doesn't match exactly.

Solution

The solution uses two DFS functions:

1. Find matching nodes: Traverse s to find nodes that match the root of t
2. Check identical trees: For each match, verify if the subtree is identical to t
3. Structure must match: Both values and structure must be exactly the same

JavaScript Solution

JavaScript Solution - DFS

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : null)
* }
*/

/**
* Check if t is a subtree of s
* @param {TreeNode} s - Main tree
* @param {TreeNode} t - Subtree to check
* @return {boolean} - True if t is a subtree of s
*/
function isSubtree(s, t) {
// Base case: if s is null, t cannot be a subtree
if (!s) return false;

// Check if current subtree of s matches t
if (isSameTree(s, t)) {
  return true;
}

// Recursively check left and right subtrees
return isSubtree(s.left, t) || isSubtree(s.right, t);
}

/**
* Check if two trees are identical
* @param {TreeNode} s - First tree
* @param {TreeNode} t - Second tree
* @return {boolean} - True if trees are identical
*/
function isSameTree(s, t) {
// Both null: identical
if (!s && !t) return true;

// One null, one not: not identical
if (!s || !t) return false;

// Values must match
if (s.val !== t.val) return false;

// Both subtrees must be identical
return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}

// Helper function to create TreeNode
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : null);
}

// Test cases
// Example 1: s = [1,3,8], t = [1,null,8]
const s1 = new TreeNode(1);
s1.left = new TreeNode(3);
s1.right = new TreeNode(8);
const t1 = new TreeNode(1);
t1.right = new TreeNode(8);
console.log('Example 1:', isSubtree(s1, t1)); // false

// Example 2: s = [7,8,3], t = [7,8,3]
const s2 = new TreeNode(7);
s2.left = new TreeNode(8);
s2.right = new TreeNode(3);
const t2 = new TreeNode(7);
t2.left = new TreeNode(8);
t2.right = new TreeNode(3);
console.log('Example 2:', isSubtree(s2, t2)); // true

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def is_subtree(s: Optional[TreeNode], t: Optional[TreeNode]) -> bool:
  """
  Check if t is a subtree of s
  
  Args:
      s: Main tree
      t: Subtree to check
      
  Returns:
      bool: True if t is a subtree of s
  """
  # Base case: if s is None, t cannot be a subtree
  if not s:
      return False
  
  # Check if current subtree of s matches t
  if is_same_tree(s, t):
      return True
  
  # Recursively check left and right subtrees
  return is_subtree(s.left, t) or is_subtree(s.right, t)

def is_same_tree(s: Optional[TreeNode], t: Optional[TreeNode]) -> bool:
  """
  Check if two trees are identical
  
  Args:
      s: First tree
      t: Second tree
      
  Returns:
      bool: True if trees are identical
  """
  # Both None: identical
  if not s and not t:
      return True
  
  # One None, one not: not identical
  if not s or not t:
      return False
  
  # Values must match
  if s.val != t.val:
      return False
  
  # Both subtrees must be identical
  return is_same_tree(s.left, t.left) and is_same_tree(s.right, t.right)

# Test cases
# Example 1: s = [1,3,8], t = [1,None,8]
s1 = TreeNode(1)
s1.left = TreeNode(3)
s1.right = TreeNode(8)
t1 = TreeNode(1)
t1.right = TreeNode(8)
print('Example 1:', is_subtree(s1, t1))  # False

# Example 2: s = [7,8,3], t = [7,8,3]
s2 = TreeNode(7)
s2.left = TreeNode(8)
s2.right = TreeNode(3)
t2 = TreeNode(7)
t2.left = TreeNode(8)
t2.right = TreeNode(3)
print('Example 2:', is_subtree(s2, t2))  # True

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (String Serialization)

Here's an alternative approach using string serialization:

JavaScript String

/**
 * String serialization approach
 */
function isSubtreeString(s, t) {
  function serialize(node) {
    if (!node) return '#';
    return node.val + ',' + serialize(node.left) + ',' + serialize(node.right);
  }
  
  const sStr = serialize(s);
  const tStr = serialize(t);
  
  return sStr.includes(tStr);
}

Python String

def is_subtree_string(s: Optional[TreeNode], t: Optional[TreeNode]) -> bool:
    """
    String serialization approach
    """
    def serialize(node: Optional[TreeNode]) -> str:
        if not node:
            return '#'
        return str(node.val) + ',' + serialize(node.left) + ',' + serialize(node.right)
    
    s_str = serialize(s)
    t_str = serialize(t)
    
    return t_str in s_str

Complexity

• Time Complexity: O(m × n) - Where m is the number of nodes in s and n is the number of nodes in t. In the worst case, we check each node in s against t.
• Space Complexity: O(m + n) - For the recursion stack. In the worst case, the recursion depth is the height of the trees.

Approach

The solution uses two DFS functions:

1. isSubtree(s, t):

   • Traverses tree s to find nodes that could be the root of t
   • For each node in s, checks if the subtree starting from that node matches t
   • Recursively checks left and right subtrees

2. isSameTree(s, t):

   • Checks if two trees are identical
   • Both must be null, or both must have same value
   • Both left and right subtrees must be identical

Key Insights

• Two-step process: Find matching nodes, then verify identical structure
• Structure matters: Values alone aren't enough, structure must match exactly
• Recursive check: Check every node in s as a potential root
• Identical trees: Use helper function to verify exact match
• Base cases: Handle null nodes correctly

Step-by-Step Example

Let's trace through Example 1: s = [1,3,8], t = [1,null,8]

s =    1
     / \
    3   8

t = 1
     \
      8

isSubtree(s=1, t=1):
  Check isSameTree(s=1, t=1):
    s.val=1, t.val=1 → match ✓
    Check isSameTree(s.left=3, t.left=null):
      s=3, t=null → not identical ✗
    Return false
  
  Check isSubtree(s.left=3, t=1):
    Check isSameTree(s=3, t=1):
      s.val=3, t.val=1 → not match ✗
    Check isSubtree(s.left=null, t=1): false
    Check isSubtree(s.right=null, t=1): false
    Return false
  
  Check isSubtree(s.right=8, t=1):
    Check isSameTree(s=8, t=1):
      s.val=8, t.val=1 → not match ✗
    Check isSubtree(s.left=null, t=1): false
    Check isSubtree(s.right=null, t=1): false
    Return false
  
  Return false

Visual Representation

Example 1: s = [1,3,8], t = [1,null,8]

s:      1          t:    1
      / \                  \
     3   8                  8

Structure mismatch:
- s has left child 3, t has no left child
- Even though values match, structure is different
Result: false

Example 2: s = [7,8,3], t = [7,8,3]

s:      7          t:    7
      / \              / \
     8   3             8   3

Perfect match:
- Values match: 7=7, 8=8, 3=3
- Structure matches: same left/right children
Result: true

Example 3: s = [7,8,3], t = [7,8,3] with extra node

s:      7          t:    7
      / \              / \
     8   3             8   3
                          /
                         1

Structure mismatch:
- t has an extra node (1) that doesn't exist in s
Result: false

Edge Cases

• t is empty: Return true (empty tree is subtree of any tree)
• s is empty: Return false (if t exists, it can't be subtree of empty tree)
• t equals s: Return true
• t is single node: Check if that value exists in s with matching structure
• t is larger than s: Return false
• Multiple matches: Check all potential matches

Important Notes

• Structure must match: Not just values, but exact structure
• Null nodes matter: Missing children must match (both null or both non-null)
• Recursive check: Check every node in s as potential root
• Two functions: isSubtree finds matches, isSameTree verifies identity
• O(m×n) worst case: When checking every node

Why Structure Matters

Example showing structure importance:

s =    1        t = 1
     / \            \
    2   3            3

Values match: 1=1, 3=3
But structure differs:
- s: 1 has left child 2, right child 3
- t: 1 has no left child, right child 3
Result: false (not a subtree)

Related Problems

• Same Tree: Check if two trees are identical
• Symmetric Tree: Different tree problem
• Maximum Depth of Binary Tree: Different problem
• Serialize and Deserialize Binary Tree: Related serialization

Takeaways

• Two-step process: Find matches, then verify identity
• Structure matters: Exact structure must match, not just values
• Recursive DFS: Check every node as potential root
• Helper function: isSameTree verifies exact match
• O(m×n) time in worst case when checking all nodes