DEV Community


Posted on

872. Leaf-Similar Trees


Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.


Time Complexity : O(n)
Space Complexity: O(n)

// DFS approach
// Staring from the left side of the tree, 
// push all leaf nodes from each root into 2 respective arrays
// Check if the values in those 2 arrays are the same
var leafSimilar = function(root1, root2) {
    const output1 = []
    const output2 = []

    dfs(root1, output1)
    dfs(root2, output2)

    return (output1.length == output2.length &&
            output1.every((val, index) => val === output2[index]));

    function dfs(node, output) {
        if(!node) return
        // Leaf node if the current ndoe has no children
        // Push value into it's respective array
        if(!node.left && !node.right) {
        if(node.left) dfs(node.left, output)
        if(node.right) dfs(node.right, output)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)