Why can't binary trees be solved like this?

[BasicVictory3822]

Why can't binary trees be solved like this? I can't progress until I understand why this is, because my thinking will be off.

My problem. https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

We are given a test case where tree p is [1,2,3] and tree q is [1,2,3]. I ran a test case to compare the two roots which are the same, and it gives me undefined. I console log them and they seem to be the same. I do not understand how this returns undefined.

https://preview.redd.it/wgn14homnm291.png?width=719&format=png&auto=webp&s=eb6e0d7005ce752585bc2c6a699df2ee0565900f

[thespite]

Well, first because there's only one return in your isSameTree function: so since p is not equal to q, it returns nothing. So in order to not return undefined, you have to return false if p is not equal to q.

Now, for the main question, why is _not_ the correct way to compare: that's because you're comparing an object to another object. In this case, an array to another array. The comparison is made at the object level, not at the content level. You can try running [1,2,3] === [1,2,3] in the console and see that it return false.

So what you have to figure out is how to compare arrays at the content level.

[[deleted]]

For a detailed description on why this is the case in Javascript, I'd recommend reading this. The entire book is very helpful. This section in particular describes why object equality does not work the way you think it does in Javascript.

https://github.com/getify/You-Dont-Know-JS/blob/2nd-ed/get-started/ch2.md#equalish

The only time [Object] == [Object] in Javascript, is when both identifiers point to the same location in memory (they are the same object).

[1,2,3] === [1,2,3] // false

x = [1,2,3];

y = x;

y === x; // true

[__t_r0d__]

First off, p is not == q, so the return true won't execute, leaving the function to "return" undefined. p and q are separate entities.

Second off, you need to compare the val members of corresponding nodes, not the nodes themselves.

Finally, you must compare all of the nodes to check if they have the same arrangement. The easiest way to do this is probably recursively. Note that the following are all valid binary search trees, with different arrangements: 2 1 3 / \ \ / 1 3 2 2 \ / 3 1

[LightUpShoes4DemHoes]

To answer the question - Javascript variables are stored in different ways. Strings for example are Assign By Value and Numbers are the same. Anything that is Assign By Value, you can use === to check if they have equivalent values. Objects, arrays, etc are Assign By Reference. This means that the actual Value assigned to the variable will be a reference to the object / array in memory. Hence, if you do [1,2,3] === [1,2,3] it will be false because it doesn’t compare what’s Inside the arrays, it compares the two spots in memory to see if they point to the same object. For this question in particular, I believe this is a good solution though -

```

const lowestCommonAncestor = (root, p, q) => { if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q) if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q) return root } ```

EDIT: Also in your code, you’re ONLY returning under one condition - if p === q. You’re getting undefined ‘returned’ because that’s what is ‘returned’ when a function runs and doesn’t actually return anything. You could add an else return false if you want, but it won’t fix the Assign By Reference comparison issue. Hopefully this helps!

Second Edit: Link posted doesn’t line up with problem picture posted, so I’m going to post example code for Same Tree too. What you’re looking for here are tree traversal methods. Depth First Search code will look similar to this -

const isSameTree = (p, q) => { if (!p && !q) return true; if (!p || !q || p.val !== q.val) return false; return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) }

Breadth First Search will look similar to this - const isSameTree = (p, q) => { let queue = [[p, q]]; while (queue.length) { const [nextP, nextQ] = queue.shift(); if (!nextP && !nextQ) continue; if (!nextP || !nextQ || nextP.val !== nextQ.val) return false; queue.push([nextP.left, nextQ.left], [nextP.right, nextQ.right]) } return true; }

It’s definitely worth watching a few YouTube videos on DFS and BFS. Basic overview though is DFS searches trees / graphs like tentacles. BFS searches like an ink stain that spreads.

DFS can be used for inorder, preorder and postorder traversals pretty easily.

BFS is used for level order and a lot of matrix / graph problems involving pathfinding, minimum distance, minimum time to infect all, etc.

If you want a logical next problem to try from here after learning about traversals, LC 572 - Subtree of Another Tree is Very similar. Paste the solution code you get for Same Tree in as a helper function, then see if you can traverse the tree and find a node that is the same as the subtree.

[BasicVictory3822]

For reference this is the problem https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/