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

Maximum Path Sum in Binary Tree

📖 Scenario: You are working on a program that analyzes a binary tree representing a network of roads with values indicating the quality of each road segment. Your goal is to find the path through the network that yields the highest total quality score.

🎯 Goal: Build a TypeScript program that creates a binary tree, sets up a helper variable, implements a function to find the maximum path sum in the tree, and prints the result.

📋 What You'll Learn

Create a binary tree using a TreeNode class with val, left, and right properties

Initialize the tree with the exact structure and values given

Create a helper variable maxSum to track the maximum path sum

Write a recursive function maxGain that calculates the maximum gain from each node

Use the function to update maxSum with the highest path sum found

Print the final maxSum value

💡 Why This Matters

🌍 Real World

Finding the maximum path sum in a binary tree can help in network optimization, such as finding the best route in a road network or the most profitable path in decision trees.

💼 Career

Understanding tree traversal and recursive algorithms is essential for software engineering roles, especially those involving data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a TreeNode class with a constructor that takes a number val and optional left and right nodes. Then create the exact binary tree with root node value 1, left child 2, and right child 3.

DSA Typescript

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

Hint

Define the TreeNode class first, then create root with left and right children.

2

Add a Helper Variable for Maximum Sum

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

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = 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 with the smallest number.

3

Implement the Maximum Path Sum Calculation

Write a recursive function called maxGain that takes a TreeNode | null parameter called node. It should return 0 if node is null. Otherwise, calculate the maximum gain from the left and right children by calling maxGain recursively and taking the maximum of 0 and the returned value. Then update maxSum with the maximum of its current value and the sum of node.val, left gain, and right gain. Finally, return node.val plus the maximum of left gain and right gain.

DSA Typescript

function maxGain(node: TreeNode | null): number {
    if (node === null) {
        return 0;
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);
    const priceNewPath = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, priceNewPath);
    return node.val + Math.max(leftGain, rightGain);
// Call maxGain and print maxSum

Hint

Use recursion to get max gain from left and right, update maxSum, and return the max gain including current node.

4

Calculate and Print the Maximum Path Sum

Call the maxGain function with the root node to start the calculation. Then print the value of maxSum using console.log(maxSum).

DSA Typescript

Hint

Call maxGain(root) to start, then print maxSum with console.log(maxSum).