Maximum Path Sum in Binary Tree in DSA Javascript - Build from Scratch

Maximum Path Sum in Binary Tree

📖 Scenario: You are working on a system that analyzes decision trees. Each node in the tree has a value representing a score. You want to find the maximum sum of values along any path in the tree. A path can start and end at any node, but it must follow parent-child connections.

🎯 Goal: Build a program that finds the maximum path sum in a binary tree. You will create the tree nodes, set up a helper variable, write the function to find the maximum path sum, and print the result.

📋 What You'll Learn

Create a binary tree with the exact structure and values given

Create a variable to track the maximum path sum

Write a recursive function called maxPathSumHelper that calculates the maximum path sum

Print the maximum path sum after processing the tree

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in decision-making systems, network analysis, and game AI where paths represent choices or routes.

💼 Career

Understanding tree traversal and recursion is essential for software engineers working on algorithms, data processing, and system design.

1

Create the Binary Tree Nodes

Create a class called TreeNode with a constructor that takes val, left, and right. Then create the binary tree with root node value 1, left child 2, and right child 3. Assign the root node to a variable called root.

DSA Javascript

// Define TreeNode class and create the tree nodes
// Your code here

Hint

Define the TreeNode class with a constructor that sets val, left, and right. Then create the root node with value 1 and children 2 and 3.

2

Create a Variable to Track Maximum Path Sum

Create a variable called maxSum and set it to Number.NEGATIVE_INFINITY to track the maximum path sum found so far.

DSA Javascript

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

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

// Create maxSum variable
// Your code here

Hint

Use let maxSum = Number.NEGATIVE_INFINITY; to start tracking the maximum path sum.

3

Write the Recursive Function to Find Maximum Path Sum

Write a function called maxPathSumHelper that takes a node as input. It should return the maximum path sum starting from that node going down. Update maxSum with the maximum path sum found including the current node and both children. Use recursion to get left and right maximum sums. Return the maximum path sum including the current node and one child or none.

DSA Javascript

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

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

let maxSum = Number.NEGATIVE_INFINITY;

function maxPathSumHelper(node) {
    // Your code here
}

Hint

Use recursion to get maximum sums from left and right children. Ignore negative sums by using Math.max(0, ...). Update maxSum with the sum including both children and current node. Return the max path sum including current node and one child.

4

Print the Maximum Path Sum

Call maxPathSumHelper with root and then print the value of maxSum.

DSA Javascript

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

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

let maxSum = Number.NEGATIVE_INFINITY;

function maxPathSumHelper(node) {
    if (node === null) return 0;
    const leftMax = Math.max(0, maxPathSumHelper(node.left));
    const rightMax = Math.max(0, maxPathSumHelper(node.right));
    const currentSum = node.val + leftMax + rightMax;
    maxSum = Math.max(maxSum, currentSum);
    return node.val + Math.max(leftMax, rightMax);
}

maxPathSumHelper(root);
// Print maxSum below
// Your code here

Hint

Call maxPathSumHelper(root) to start the recursion. Then print maxSum to see the maximum path sum.