Leaf-Similar Trees

I will be walking through the algorithm to solve the problem of 2 nodes where we are told to find if the leaf of both nodes are the same. Basically, we are given 2 TreeNodes instances and we need to find out if the leaf are the same. Moreover, the leafs should be exactly the same from left to right.

In this example, we observe that the leafs are not the same since for the first instance the node 5 left child is 6 but on the second instance is in fact 7.

In this example we can observe that all leaf nodes are the same- each indexed holds the same value for both.

Algorithm

The first thing that comes in mind is we need to traverse through both instances to know the leaf nodes of each instance. Also, since we are being asked only for the values we can simply store it an array since we can verify its order by the index. We do not need to sort the array as we will be pushing the values while traversing. the only order that matter is the order that we pushed the values. Since we will be using the same traversal function, that would not result in a different order. That being said, our recursive function should pass an array corresponding to the leaf nodes of each instance.

Once we traverse both instances and have both arrays filled with values, the first intuition is if both are the same then then length should be the same. We could verify this at O(1) times before iterating through the array. If both are the same length then we should iterate but return false soon as one of the values are not the same.

Original Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function (root1, root2) {

    if (!root1 || !root2) {
        return false;
    }

    let leaf_Nodes_1 = [];
    let leaf_nodes_2 = [];

    const helper = (node, leaves) => {
        if (!node) return;

        if (node && node.left === null && node.right === null) {
            leaves.push(node.val);
        }

        helper(node.left, leaves);
        helper(node.right, leaves);
    };

    helper(root1, leaf_Nodes_1);
    helper(root2, leaf_nodes_2);
    
    return (
        leaf_Nodes_1.length === leaf_nodes_2.length &&   leaf_Nodes_1.every((val,index)=> val === leaf_nodes_2[index])
    );

};        

Input

root1 =

[3,5,1,6,2,9,8,null,null,7,4]

root2 =

[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

Output

true

Expected

true

Accepted

Runtime: 61 ms

Case 1

Case 2

Input

root1 =

[1,2,3]

root2 =

[1,3,2]

Output

false

Expected

false