Same Binary Tree - Leetcode 100

leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[ARKGAMING]

No need for the complex if to check if only one is null. You already checked if both are null simultaneously, so a simple or operation will tell you if exactly one of them is null without needing to check that the other one isn't

[M-sqkk]

You can just write “if not p or not q” in the second check, cause you already checked if both aren’t there in the previous check

[RukopisyNarnie]

Depends on your implementatin, but in most cases, you can just compare underlying data. -> for (size_t = 0; i < len; ++i) one[i] == two[i] ? continue : return false; return true;

[paradise-flossed]

Remember to discuss the potential upper bound of recursion limits if taking this approach and discuss alternative implementations like using a stack if you want to keep doing DFS or a queue if you prefer a BFS implementation.

This solution would work, but it would leave room for some follow up questions you’ll have to navigate. Be prepared for those. 😊

[Bonnbon]

I wish I’ll be asked something this easy in my interviews

[DSamp]

On a lower level, wouldn't you just flatten the two binary trees to arrays (or rather get references to their backing arrays) and do a length comparison and memcmp()?

[NO]

Я думал там какой-то заумный алгоритм будет, а оказывается достаточно знать, что 4!=5 😂

[mikee.]

This only makes two trees equal when they are equally balanced, wouldn't you rather want to check if they contain the same elements, no matter the balancing? In that case iterate from small to large and check every element

[tgr]

That’s easy. Now do the same with two non-tree graphs with repeating values in nodes and no specified root

[alxjones]

The inner function doesn't do anything the outer function couldn't already do. The second and third check can be combined using getattr to get val when the node exists and None otherwise.

```
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return (
True if not p and not q else
False if not getattr(p, 'val', None) == getattr(q, 'val', None) else
self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
)
```

[mihaiblidaru]

To check if something is null you should use if x is not None. False (bool) is not the same as null(None in python)

[nolanrata]

I think the second long boolean expression can be shortened to "not p or not q" since we already know that "not p and not q" is false.

[rikvandonselaar]

'if p - q = 0 return true. else return false' use a line of code that does this recursively.

[ItachiUchiha-mgyp]

Can we also do, check if both have the same inorder traversal?

[m____]

same(a, b):
a is null && b is null
|| (a.val == b.val
&& same(a.left, b.left)
&& same(a.right, b.right))

[YKkUzZ]

Guys.... Of you do not have P, consider visiting your doctor.

[FrozenKnight]

While this would work there is a strange case where you could have a flipped tree, which would technically be the same but would fail your test.

[durgeshnandan]

The first two checks could be combined like

if not p or not q :
return p == q

[michaelroditis]

I just want to say that for the second if statement you can wright if not q or not p since you know that both ain't null at the same time. Or you could you xor if you feel fancy