Quick question about leetcode 101.Symmetric Tree

Question

I was wondering why the first dfs returns false and the second returns true. From my understanding || operator returns true if one of the expressions is true. thanks, guys!

var isSymmetric = function(root) {
    if (!root) return true;

    return dfs(root.left, root.right);
};

const dfs = (left, right) => {
    if (left.left || right.right) {
        return left.left === right.right;
    }
    if (left.val !== right.val) return false;

    return dfs(left.left, right.right) && dfs(left.right, right.left)
}

const dfs = (left, right) => {
    if (!left.left || !right.right) {
        return left.left === right.right;
    }
    if (left.val !== right.val) return false;

    return dfs(left.left, right.right) && dfs(left.right, right.left)
}

With the first one you immediately get into the `if` for the root node. And since the left and right nodes are *different*, it returns false. With the second, you only get into the `if` for *leaf nodes* and then it returns `true` because `left.left` and `right.right` are the same value that signals "missing" - either `null` or `undefined`. — VLAZ, Jan 05 '21 at 06:26
@VLAZ Thank you for helping me! I think I need a clarification why the first one immediately goes into `if`? if statement is checking if left.left or right.right exist? And I'm not too sure with the second (you mean second dfs logic?) — Seong Choi, Jan 05 '21 at 06:34
In the first case you check if either `left` or `right` exists. For the root node (assuming the tree more nodes) that is going to be true. However, those would be two *different objects*, so they will never be equal. The second `dfs` logic only goes in the `if` if *neither* `left.left` *nor* `right.right` exist. So, if both are missing. This will *only* happen if `left` and `right` are leaf nodes - it will never trigger for the root node (again, assuming there are more nodes). — VLAZ, Jan 05 '21 at 06:42
@VLAZ isn't first case is checking if `root.left.left` and `root.left.right` node exist? I'm confuse by check if either `left` or `right`. And if its two different object it should never be equal but second dfs logic pass all the test cases. — Seong Choi, Jan 05 '21 at 06:48
*If* `root.left.left` and `root.right.right` exist then you compare `root.left.left === root.right.right` [which will never be true](https://stackoverflow.com/questions/11704971/why-are-two-identical-objects-not-equal-to-each-other). However if *both* `node.left.left` and `node.right.right` are `null` (or `undefined` - whatever marks "nothing" in your case) then `null === null` (or `undefined === undefined`) is `true`. — VLAZ, Jan 05 '21 at 06:53
@VLAZ sorry I miss wrote `root.left.left` and `root.right.right` I wanted to check `root.left` and `root.right` :( — Seong Choi, Jan 05 '21 at 07:03

score 0 · Accepted Answer · answered Jan 05 '21 at 07:16

Here is a sample tree with the nodes labelled for ease.

     A
   /   \
  B     C
 / \   / \
D   E F   G

Using this code:

const dfs = (left, right) => {
    if (left.left || right.right) {
        return left.left === right.right;
    }
    if (left.val !== right.val) return false;

    return dfs(left.left, right.right) && dfs(left.right, right.left)
}

Starting from the root A, left would be B and right would be C.

The first if would check whether left.left (which is D) and right.right (which is G) exist. Since they do, it tries to directly compare the nodes.

Two different objects are never equal to each other

const D = {val: "X"};
const G = {val: "X"};

console.log(D === G);

Which means that the if will immediately return false for any tree.

Using this condition instead radically changes the semantics:

if (!left.left || !right.right) {
    return left.left === right.right;
}

Now the code checks whether both left.left and right.right are missing. Given the tree above, this is not true for the root node A, since both D and G are there. The condition would only trigger for a tree of this shape:

  X
 / \
Y   Z

Starting with X, left would be Y and right would be Z.

In this case left.left and right.right are both the same value - most likely either null or undefined (depending on how the tree was built up).

console.log(null === null);
console.log(undefined === undefined);

Therefore, in the second case it works but by accident only because missing nodes are the same.

Quick question about leetcode 101.Symmetric Tree

1 Answers1