How to use optimized DFS( Depth first search) In Javascript

Using Postorder Traversal

In this approach we start with the base case. If the current node is null, return 0. For each node, calculate the maximum path sum that includes that node. Recursively traverse the left and right subtrees to get their maximum path sums. Update the global maximum sum if a new maximum path sum is found. Return the maximum path sum including the current node to the parent.

Example: To demonstrate finding the maximum path sum between to leaves of a binary tree using Javascript.

JavaScript

class TreeNode {
    constructor(val = 0, left = null, right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    maxPathSum(root) {
        let ans = [-Infinity];
        // Initialize with negative 
        // infinity for comparison

        function DFS(root)
        {
            if (root === null)
            {
                return 0;
            }
            let lmax = Math
                .max(0, DFS(root.left));
            let rmax = Math
                .max(0, DFS(root.right));

            // Update the overall 
            // maximum path sum
            ans[0] = Math
                .max(ans[0], root.val + lmax + rmax);

            // Return the maximum path sum
            // that starts from the current node
            return root
                .val + Math
                    .max(lmax, rmax);
        }

        // Call the DFS function
        //  on the root node
        DFS(root);

        // Return the final maximum path sum
        return ans[0] !== -Infinity ? ans[0] : 0;
        // If ans is still -Infinity, return 0
    }
}

// Example input
let root = new TreeNode(-10);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

let solution = new Solution();
console.log(solution.maxPathSum(root));

Time Complexity: O(N)

Space Complexity: O(H), where H is the height of the tree (O(log N) for a balanced tree and O(N) for a skewed tree).

Find the maximum path sum between two leaves of a binary tree using JavaScript

Given the root of a binary tree, return the maximum path sum of any non-empty path. A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path.

Maximum path sum is 42.

Table of Content