Leetcode•May 31, 2025

Subtree of Another Tree

Hazrat Ali

Leetcode

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false


Solution
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
const isSubtree = (s, t) => {
  const stack = [s];

  while (stack.length) {
    const node = stack.pop();

    if (node.val === t.val && isSameTree(node, t)) {
      return true;
    }

    if (node.left) {
      stack.push(node.left);
    }

    if (node.right) {
      stack.push(node.right);
    }
  }

  return false;
};

const isSameTree = (s, t) => {
  if (!s && !t) {
    return true;
  }

  if (!s || !t || s.val !== t.val) {
    return false;
  }

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



Comments