Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Same Tree

Problem Statement

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 met following two conditions:

  1. Both tree are structurally identical.
  2. Each corresponding node on both the trees have the same value.

Example 1:

Given the following two binary trees:

Output: true

Explanation: Both trees are structurally identical and have same values.

Example 2:

Given the following two binary trees:

Output: false

Explanation: Trees are structurally different.

.....

.....

.....

Like the course? Get enrolled and start learning!
Mahendra Reddy

Mahendra Reddy

· 2 years ago

When multiple threads are updating ***isSame*** variable

isSame &= isSameTreeMultiThreaded(p.left, q.left, numThreads/2);
SIMILAR TO
isSame = isSame & isSameTreeMultiThreaded(p.left, q.left, numThreads/2);
  1. It reads isSame which is thread safe gives latest value due to primitive
  2. & operator with isSame variable ( one more, by the time it evaluates through recursive function, isSame variable could be outdated )
  3. Updating isSame variable which is thread safe due to primitive

But, All the above 3 steps together is not atomic.

Consider the scenario:

isSame is true by default,

  1. Thread-1 reads as true
  2. Thread-2 reads as true
  3. Thread-1 receives false from recursive function and updates it with *false
M

Mi Nguyen

· 4 years ago

Where is python :((

R

Ray

· 4 years ago

As a non-Java user, I expect other language solutions (python, JS, etc) presented here since they are present in the other chapters & courses. Thank you

J

Jason

· 4 years ago

I would love a C++ solution for the thread safe questions!

Show 1 reply
M

Mike Xu

· 3 years ago

For the Space Complexity of the non-multi-threaded solution, why does the stack take O(N) space but to store nodes we need O(H)? O(N) and O(H) should be the same, right?

Show 1 reply