Subtree of Another Tree

Photo by Matthew Smith on Unsplash

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

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

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

Algorithm -

  1. Find the node in the root tree which matches with the root of subTree.
  2. Once found we can check the subtree of root tree is same as subTree.
  3. We first compare the root with subTree.
  4. If both the trees are not same, go to the left of root and compare the left subtree with the given subTree.
  5. If in step 4 we did not find the same tree, we compare right subtree with input subTree.
  6. If we did not find match at step 4 and 5, we recursively traverse the left and right subtree of root and check for is same tree.

Runtime: 130 ms.

Memory Usage: 47.6 MB

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Rage Alert and @debouncedtask

Insights on integrating the Rosetta API developed by Coinbase

You are the only one who can schedule your time.

Everything is an object in Python

Session Authentication with Lambda and DynamoDB

Knowledge Is Dead, Long Live Learning

How to Get a Log of DNS Queries with Sysmon

Complete Guide to Hire a Node JS Developer in This Digital Age

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Google / Amazon /Microsoft Interview Question — 200. Number of Islands — Leetcode

Design HashMap without using any built-in hash table libraries.

Shopify Developer Interview Experience

Leetcode 153 — Find Minimum in Rotated Sorted Array