Welcome to Subscribe On Youtube

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript

• /*
  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);
  	    }
  	}
  }
  
  ############
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      public boolean isSubtree(TreeNode root, TreeNode subRoot) {
          if (root == null) {
              return false;
          }
          return dfs(root, subRoot) || isSubtree(root.left, subRoot)
              || isSubtree(root.right, subRoot);
      }
  
      private boolean dfs(TreeNode root1, TreeNode root2) {
          if (root1 == null && root2 == null) {
              return true;
          }
          if (root1 == null || root2 == null) {
              return false;
          }
          return root1.val == root2.val && dfs(root1.left, root2.left)
              && dfs(root1.right, root2.right);
      }
  }
  

• // OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray
  // Time: O(ST) where S and T are the node count of s and t.
  // Space: O(H) where H is the height of s.
  class Solution {
  private:
      bool isSameTree(TreeNode* s, TreeNode* t) {
          return (!s && !t) || (s && t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right));
      }
  public:
      bool isSubtree(TreeNode* s, TreeNode* t) {
          return isSameTree(s, t) || (s && (isSubtree(s->left, t) || isSubtree(s->right, t)));
      }
  };
  

• # 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
  class Solution:
      def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
          def dfs(root1, root2):
              if root1 is None and root2 is None:
                  return True
              if root1 is None or root2 is None:
                  return False
              return (
                  root1.val == root2.val
                  and dfs(root1.left, root2.left)
                  and dfs(root1.right, root2.right)
              )
  
          if root is None:
              return False
          return (
              dfs(root, subRoot)
              or self.isSubtree(root.left, subRoot)
              or self.isSubtree(root.right, subRoot)
          )
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
    def isSubtree(self, s, t):
      """
      :type s: TreeNode
      :type t: TreeNode
      :rtype: bool
      """
  
      def serialize(root):
        ans = []
        stack = [(root, 1)]
        while stack:
          node, p = stack.pop()
          if not node:
            ans.append("#")
            continue
          if p == 0:
            ans.append("|" + str(node.val))
          else:
            stack.append((node.right, 1))
            stack.append((node.left, 1))
            stack.append((node, 0))
        return ",".join(ans)
  
      return serialize(t) in serialize(s)
  
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
  	if root == nil {
  		return false
  	}
  	var dfs func(root1, root2 *TreeNode) bool
  	dfs = func(root1, root2 *TreeNode) bool {
  		if root1 == nil && root2 == nil {
  			return true
  		}
  		if root1 == nil || root2 == nil {
  			return false
  		}
  		return root1.Val == root2.Val && dfs(root1.Left, root2.Left) && dfs(root1.Right, root2.Right)
  	}
  	return dfs(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
  }
  

• /**
   * Definition for a binary tree node.
   * class TreeNode {
   *     val: number
   *     left: TreeNode | null
   *     right: TreeNode | null
   *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.left = (left===undefined ? null : left)
   *         this.right = (right===undefined ? null : right)
   *     }
   * }
   */
  
  const dfs = (root: TreeNode | null, subRoot: TreeNode | null) => {
      if (root == null && subRoot == null) {
          return true;
      }
      if (root == null || subRoot == null || root.val !== subRoot.val) {
          return false;
      }
      return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
  };
  
  function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
      if (root == null) {
          return false;
      }
      return (
          dfs(root, subRoot) ||
          isSubtree(root.left, subRoot) ||
          isSubtree(root.right, subRoot)
      );
  }
  
  

• /**
   * 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 : right)
   * }
   */
  /**
   * @param {TreeNode} root
   * @param {TreeNode} subRoot
   * @return {boolean}
   */
  var isSubtree = function (root, subRoot) {
      if (!root) return false;
      let dfs = function (root1, root2) {
          if (!root1 && !root2) {
              return true;
          }
          if (!root1 || !root2) {
              return false;
          }
          return (
              root1.val == root2.val &&
              dfs(root1.left, root2.left) &&
              dfs(root1.right, root2.right)
          );
      };
      return (
          dfs(root, subRoot) ||
          isSubtree(root.left, subRoot) ||
          isSubtree(root.right, subRoot)
      );
  };
  
  

• // Definition for a binary tree node.
  // #[derive(Debug, PartialEq, Eq)]
  // pub struct TreeNode {
  //   pub val: i32,
  //   pub left: Option<Rc<RefCell<TreeNode>>>,
  //   pub right: Option<Rc<RefCell<TreeNode>>>,
  // }
  //
  // impl TreeNode {
  //   #[inline]
  //   pub fn new(val: i32) -> Self {
  //     TreeNode {
  //       val,
  //       left: None,
  //       right: None
  //     }
  //   }
  // }
  use std::rc::Rc;
  use std::cell::RefCell;
  impl Solution {
      fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, sub_root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
          if root.is_none() && sub_root.is_none() {
              return true;
          }
          if root.is_none() || sub_root.is_none() {
              return false;
          }
          let root = root.as_ref().unwrap().borrow();
          let sub_root = sub_root.as_ref().unwrap().borrow();
          root.val == sub_root.val
              && Self::dfs(&root.left, &sub_root.left)
              && Self::dfs(&root.right, &sub_root.right)
      }
  
      fn help(
          root: &Option<Rc<RefCell<TreeNode>>>,
          sub_root: &Option<Rc<RefCell<TreeNode>>>,
      ) -> bool {
          if root.is_none() {
              return false;
          }
          Self::dfs(root, sub_root)
              || Self::help(&root.as_ref().unwrap().borrow().left, sub_root)
              || Self::help(&root.as_ref().unwrap().borrow().right, sub_root)
      }
  
      pub fn is_subtree(
          root: Option<Rc<RefCell<TreeNode>>>,
          sub_root: Option<Rc<RefCell<TreeNode>>>,
      ) -> bool {
          Self::help(&root, &sub_root)
      }
  }
  
  

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript

• /**
   * 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);
      }
  }
  
  ############
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      public boolean isSubtree(TreeNode root, TreeNode subRoot) {
          if (root == null) {
              return false;
          }
          return dfs(root, subRoot) || isSubtree(root.left, subRoot)
              || isSubtree(root.right, subRoot);
      }
  
      private boolean dfs(TreeNode root1, TreeNode root2) {
          if (root1 == null && root2 == null) {
              return true;
          }
          if (root1 == null || root2 == null) {
              return false;
          }
          return root1.val == root2.val && dfs(root1.left, root2.left)
              && dfs(root1.right, root2.right);
      }
  }
  

• // OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray
  // Time: O(ST) where S and T are the node count of s and t.
  // Space: O(H) where H is the height of s.
  class Solution {
  private:
      bool isSameTree(TreeNode* s, TreeNode* t) {
          return (!s && !t) || (s && t && s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right));
      }
  public:
      bool isSubtree(TreeNode* s, TreeNode* t) {
          return isSameTree(s, t) || (s && (isSubtree(s->left, t) || isSubtree(s->right, t)));
      }
  };
  

• # 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
  class Solution:
      def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
          def dfs(root1, root2):
              if root1 is None and root2 is None:
                  return True
              if root1 is None or root2 is None:
                  return False
              return (
                  root1.val == root2.val
                  and dfs(root1.left, root2.left)
                  and dfs(root1.right, root2.right)
              )
  
          if root is None:
              return False
          return (
              dfs(root, subRoot)
              or self.isSubtree(root.left, subRoot)
              or self.isSubtree(root.right, subRoot)
          )
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
    def isSubtree(self, s, t):
      """
      :type s: TreeNode
      :type t: TreeNode
      :rtype: bool
      """
  
      def serialize(root):
        ans = []
        stack = [(root, 1)]
        while stack:
          node, p = stack.pop()
          if not node:
            ans.append("#")
            continue
          if p == 0:
            ans.append("|" + str(node.val))
          else:
            stack.append((node.right, 1))
            stack.append((node.left, 1))
            stack.append((node, 0))
        return ",".join(ans)
  
      return serialize(t) in serialize(s)
  
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
  	if root == nil {
  		return false
  	}
  	var dfs func(root1, root2 *TreeNode) bool
  	dfs = func(root1, root2 *TreeNode) bool {
  		if root1 == nil && root2 == nil {
  			return true
  		}
  		if root1 == nil || root2 == nil {
  			return false
  		}
  		return root1.Val == root2.Val && dfs(root1.Left, root2.Left) && dfs(root1.Right, root2.Right)
  	}
  	return dfs(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
  }
  

• /**
   * Definition for a binary tree node.
   * class TreeNode {
   *     val: number
   *     left: TreeNode | null
   *     right: TreeNode | null
   *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.left = (left===undefined ? null : left)
   *         this.right = (right===undefined ? null : right)
   *     }
   * }
   */
  
  const dfs = (root: TreeNode | null, subRoot: TreeNode | null) => {
      if (root == null && subRoot == null) {
          return true;
      }
      if (root == null || subRoot == null || root.val !== subRoot.val) {
          return false;
      }
      return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
  };
  
  function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
      if (root == null) {
          return false;
      }
      return (
          dfs(root, subRoot) ||
          isSubtree(root.left, subRoot) ||
          isSubtree(root.right, subRoot)
      );
  }
  
  

• /**
   * 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 : right)
   * }
   */
  /**
   * @param {TreeNode} root
   * @param {TreeNode} subRoot
   * @return {boolean}
   */
  var isSubtree = function (root, subRoot) {
      if (!root) return false;
      let dfs = function (root1, root2) {
          if (!root1 && !root2) {
              return true;
          }
          if (!root1 || !root2) {
              return false;
          }
          return (
              root1.val == root2.val &&
              dfs(root1.left, root2.left) &&
              dfs(root1.right, root2.right)
          );
      };
      return (
          dfs(root, subRoot) ||
          isSubtree(root.left, subRoot) ||
          isSubtree(root.right, subRoot)
      );
  };
  
  

• // Definition for a binary tree node.
  // #[derive(Debug, PartialEq, Eq)]
  // pub struct TreeNode {
  //   pub val: i32,
  //   pub left: Option<Rc<RefCell<TreeNode>>>,
  //   pub right: Option<Rc<RefCell<TreeNode>>>,
  // }
  //
  // impl TreeNode {
  //   #[inline]
  //   pub fn new(val: i32) -> Self {
  //     TreeNode {
  //       val,
  //       left: None,
  //       right: None
  //     }
  //   }
  // }
  use std::rc::Rc;
  use std::cell::RefCell;
  impl Solution {
      fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, sub_root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
          if root.is_none() && sub_root.is_none() {
              return true;
          }
          if root.is_none() || sub_root.is_none() {
              return false;
          }
          let root = root.as_ref().unwrap().borrow();
          let sub_root = sub_root.as_ref().unwrap().borrow();
          root.val == sub_root.val
              && Self::dfs(&root.left, &sub_root.left)
              && Self::dfs(&root.right, &sub_root.right)
      }
  
      fn help(
          root: &Option<Rc<RefCell<TreeNode>>>,
          sub_root: &Option<Rc<RefCell<TreeNode>>>,
      ) -> bool {
          if root.is_none() {
              return false;
          }
          Self::dfs(root, sub_root)
              || Self::help(&root.as_ref().unwrap().borrow().left, sub_root)
              || Self::help(&root.as_ref().unwrap().borrow().right, sub_root)
      }
  
      pub fn is_subtree(
          root: Option<Rc<RefCell<TreeNode>>>,
          sub_root: Option<Rc<RefCell<TreeNode>>>,
      ) -> bool {
          Self::help(&root, &sub_root)
      }
  }
  
  

All Problems

All Solutions