How to use Postorder Traversal In Javascript

Using optimized DFS( Depth first search)

In this approach we traverse each node of the tree using inorder, preorder, or postorder traversal. For each node, consider it as the root and recursively find the maximum left path sum and maximum right path sum. Update the final answer with the maximum value found.

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

JavaScript

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

// Helper function to find the maximum 
// path sum from the given node to any leaf
function PathSum(node) 
{
    if (node === null) return 0;
    if (node.left === null && node.right === null)
        return node.val;
    // Leaf node

    const leftSum = node
        .left ? PathSum(node.left) : -Infinity;
    const rightSum = node
        .right ? PathSum(node.right) : -Infinity;

    return node
        .val + Math
            .max(leftSum, rightSum);
}

// Function to find the maximum path sum between 
// two leaf nodes considering the given node as root
function maxPathSumNode(node)
{
    if (node === null) return -Infinity;
    if (node.left === null || node.right === null)
        return -Infinity;

    const leftSum = PathSum(node.left);
    const rightSum = PathSum(node.right);

    return leftSum + rightSum + node.val;
}

// Function to traverse the tree
//  and update the maximum path sum
function traverseTree(node, maxSum) {
    if (node === null) return;

    const currentMax = maxPathSumNode(node);
    if (currentMax > maxSum.value) maxSum.
    value = currentMax;

    traverseTree(node.left, maxSum);
    traverseTree(node.right, maxSum);
}

// The main function to return
//  the maximum sum between two leaves
function maxSum(root) {
    let maxSum = { value: -Infinity };
    traverseTree(root, maxSum);
    return maxSum.value;
}

// Utility function to create a new tree node
function newNode(data) {
    return new TreeNode(data);
}

// Example usage
const root = newNode(-10);
root.left = newNode(9);
root.right = newNode(20);
root.right.left = newNode(15);
root.right.right = newNode(7);

console.log("Max path sum of the given binary tree is " + maxSum(root));

Time Complexity: O(N^2) in the worst case due to repeated subtree traversals.

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