Category: Binary Tree

Categories
Binary Tree Depth First Search Leetcode Recursion

Path Sum II

let pathSum = function(root, sum, results = [], result = []) {

    if (!root) return results;
    if (sum - root.val === 0 && !root.left && !root.right) {
        results.push([...result, root.val]);
    }

    pathSum(root.left, sum - root.val, results, [...result, root.val]);
    pathSum(root.right, sum - root.val, results, [...result, root.val]);
    return results;
};
Categories
Binary Tree Depth First Search Leetcode Recursion

Path Sum I

let hasPathSum = function(root, sum) {

    if (!root) return false;
    if (sum - root.val === 0 && !root.left && !root.right) return true;

    return hasPathSum(root.left, sum - root.val)
        || hasPathSum(root.right, sum - root.val);
};
Categories
Binary Tree Leetcode Recursion

Is Subtree

let isSubtree = function(mainTree, subTree) {

    function isSame(left, right) {
        if (left === right) return true;
        if (left === null && right !== null) return false;
        if (left !== null && right === null) return false;
        if (left.val !== right.val) return false;
        return isSame(left.left, right.left)
            && isSame(left.right, right.right);
    }

    if (mainTree === subTree) return true;
    if (!mainTree) return false;
    if (isSame(mainTree, subTree)) return true;

    return isSubtree(mainTree.left, subTree) || isSubtree(mainTree.right, subTree);
};
Categories
Binary Tree Breadth First Search

Level Order ZigZag Traversal

function levelOrderZigzag(root) {

    let queue = [root], result = [], direction = 0;
    function process(node) {
        result.push(node.val); //?
    }

    while (queue.length) {
        let level = [];
        while(queue.length) {
            const node = queue.pop();
            process(node);
            if (direction === 0) {
                if (node.left) level.push(node.left);
                if (node.right) level.push(node.right);
            }
            else {
                if (node.right) level.push(node.right);
                if (node.left) level.push(node.left);
            }
        }
        direction ^= 1;
        queue = level;
    }

    return result; //?
}
Categories
Binary Tree Breadth First Search

Level Order Tree Traversal

function levelOrder(root) {

    let queue = [root], result = [];
    function process(node) {
        result.push(node.val);
    }

    while (queue.length) {
        const node = queue.pop();
        process(node);
        if (node.left) queue.unshift(node.left);
        if (node.right) queue.unshift(node.right);
    }

    return result; //?
}
Categories
Binary Tree Leetcode Recursion

Is Same Tree

let isSameTree = function(p, q) {

    if (p === q) return true;
    if (p?.val !== q?.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
Categories
Binary Tree Leetcode Recursion

Invert a Binary Tree

let invertTree = function(root) {

    if (root) {
        const right = root.right;
        root.right = invertTree(root.left)
        root.left = invertTree(right)
        return root;
    }
    return null;
};