Same Tree

Photo by Wim van 't Einde on Unsplash

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Input: p = [1,2,3], q = [1,2,3]
Output: true
Input: p = [1,2], q = [1,null,2]
Output: false
Input: p = [1,2,1], q = [1,1,2]
Output: false

Approach 1: Recursion

Intuition

The simplest strategy here is to use recursion. Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.

Approach 2: Iteration

Intuition

Start from the root and then at each iteration pop the current node out of the queue. Then do the same checks as in the approach 1 :

  • p and p are not Null
  • p.val is equal to q.val

and if checks are OK, push the child nodes.

Complexity Analysis

  • Time complexity : O(N) since each node is visited exactly once.
  • Space complexity : O(log(N)) in the best case of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a queue.

--

--

--

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

That Time A Guy Broke The Internet.

How to Integrate Multi Tenant Architecture in Laravel Framework Using Tenancy\Tenancy

Dynamic Data Race Detection using Eraser.

DevOps monitoring tools at a Glance

APM Tools

I just make a poor man TikTok app.

Failure Modes for distributed applications

FMECA

Best Visual Studio Code Extensions for Web Development

Best Visual Studio Code Extensions for Web Development

Bath Ruby Conference

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

Valid Palindrome II

Trapping Rainwater Problem: Three different approaches (brute to optimized)

raining gif

DFS recursive solution to find Lowest Common Ancestor (LCA) of a Binary Tree

The All-New Interview Preparation Platform