Same Tree, Iterative Solution, JavaScript

Question

I need to check if two given binary trees are the same. Here's an iterative solution that I wrote:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */

var isSameTree = function(p, q) {
    const nodePair = [p, q]
    const nodes = []

    if(p && q) nodes.push(nodePair) 
    else if (!p && !q) return true
    else return false

    while(nodes.length) {
        const lastNodePair = nodes.pop()

       if(
           (lastNodePair[0].val !== lastNodePair[1].val)
            || (lastNodePair[0].left && !lastNodePair[1].left)
            || (!lastNodePair[0].left && lastNodePair[1].left)
            || (lastNodePair[0].right && !lastNodePair[1].right)
            || (!lastNodePair[0].right && lastNodePair[1].right)
       ) return false

        if(lastNodePair[0].left && lastNodePair[1].left) {
            nodes.push([lastNodePair[0].left, lastNodePair[1].left])   
        }
        else if(lastNodePair[0].right && lastNodePair[1].right) {
            nodes.push([lastNodePair[0].right, lastNodePair[1].right])        
        }
    }
    return true
};

It passes 56 out of 57 test cases, but not this case, which is supposed to be false:

[390,255,2266,-273,337,1105,3440,-425,4113,null,null,600,1355,3241,4731,-488,-367,16,null,565,780,1311,1755,3075,3392,4725,4817,null,null,null,null,-187,152,395,null,728,977,1270,null,1611,1786,2991,3175,3286,null,164,null,null,4864,-252,-95,82,null,391,469,638,769,862,1045,1138,null,1460,1663,null,1838,2891,null,null,null,null,3296,3670,4381,null,4905,null,null,null,-58,null,null,null,null,null,null,null,null,734,null,843,958,null,null,null,1163,1445,1533,null,null,null,2111,2792,null,null,null,3493,3933,4302,4488,null,null,null,null,null,null,819,null,null,null,null,1216,null,null,1522,null,1889,2238,2558,2832,null,3519,3848,4090,4165,null,4404,4630,null,null,null,null,null,null,1885,2018,2199,null,2364,2678,null,null,null,3618,3751,null,4006,null,null,4246,null,null,4554,null,null,null,1936,null,null,null,null,2444,2642,2732,null,null,null,null,null,null,null,4253,null,null,null,null,2393,2461,null,null,null,null,4250,null,null,null,null,2537]

[390,255,2266,-273,337,1105,3440,-425,4113,null,null,600,1355,3241,4731,-488,-367,16,null,565,780,1311,1755,3075,3392,4725,4817,null,null,null,null,-187,152,395,null,728,977,1270,null,1611,1786,2991,3175,3286,null,164,null,null,4864,-252,-95,82,null,391,469,638,769,862,1045,1138,null,1460,1663,null,1838,2891,null,null,null,null,3296,3670,4381,null,4905,null,null,null,-58,null,null,null,null,null,null,null,null,734,null,843,958,null,null,null,1163,1445,1533,null,null,null,2111,2792,null,null,null,3493,3933,4302,4488,null,null,null,null,null,null,819,null,null,null,null,1216,null,null,1522,null,1889,2238,2558,2832,null,3519,3848,4090,4165,null,4404,4630,null,null,null,null,null,null,1885,2018,2199,null,2364,2678,null,null,null,3618,3751,null,4006,null,null,4246,null,null,4554,null,null,null,1936,null,null,null,null,2444,2642,2732,null,null,null,null,null,null,null,4253,null,null,null,null,2461,2393,null,null,null,null,4250,null,null,null,null,2537]

I'd like to stick with an iterative solution if possible.

what is the difference between 2 array you provided, looks like same to me? — Narendra
– Narendra, Commented Oct 10, 2018 at 1:01
I don't understand. Aren't the sample data lists not a trees? And @Narendra a 2461 was switched with a 2393 near the end. — clabe45
– clabe45, Commented Oct 10, 2018 at 1:06
@clabe45 They are arrays of the tree nodes' values. You can see the original question by searching by "same tree" in LeetCode. — Jaeeun Lee
– Jaeeun Lee, Commented Oct 10, 2018 at 1:11
Just out of curiosity, why do you want to stick with an iterative solution? A recursive solution -- which matches the data structure more closely -- is much simpler. — Scott Sauyet
– Scott Sauyet, Commented Oct 10, 2018 at 2:01

Firman Wijaya · Accepted Answer · 2018-10-10 01:54:19Z

2

You are comparing only the left children of both trees OR the right children of both trees because you have else if there when comparing children. Remove the else. Because, if both this.left and this.right from both trees are not null, the right children will not be compared because you have else there. Only the left children are compared

    if(lastNodePair[0].left && lastNodePair[1].left) {
        nodes.push([lastNodePair[0].left, lastNodePair[1].left])   
    }
    if(lastNodePair[0].right && lastNodePair[1].right) {
        nodes.push([lastNodePair[0].right, lastNodePair[1].right])        
    }

answered Oct 10, 2018 at 1:54

Firman Wijaya

1867 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Same Tree, Iterative Solution, JavaScript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related