Path Sum Root to Leaf in Binary Tree in DSA Typescript - Build from Scratch

Path Sum Root to Leaf in Binary Tree

📖 Scenario: You are working with a simple binary tree that represents paths in a garden. Each node has a number representing the cost to walk through that part of the garden. You want to find if there is a path from the entrance (root) to any exit (leaf) where the total cost equals a specific target.

🎯 Goal: Build a TypeScript program that checks if there is a root-to-leaf path in a binary tree where the sum of node values equals a given target sum.

📋 What You'll Learn

Create a binary tree with the exact structure and values given.

Add a target sum variable with the exact value given.

Write a function called hasPathSum that takes the root of the tree and the target sum, and returns true if such a path exists, otherwise false.

Print the result of calling hasPathSum with the tree and target sum.

💡 Why This Matters

🌍 Real World

Finding paths with specific sums in trees can be used in decision-making systems, route planning, and analyzing hierarchical data.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles, especially those involving data structures, algorithms, and problem-solving.

1

Create the binary tree structure

Create a class called TreeNode with val, left, and right properties. Then create the binary tree with root node value 5, left child 4, right child 8, left child of 4 is 11, and leaves 7 and 2 as children of 11. The right child 8 has children 13 and 4, and the right child 4 has a right child 1. Use exact variable names TreeNode and root.

DSA Typescript

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

Hint

Define the TreeNode class with a constructor that sets val, left, and right. Then build the tree exactly as described using new TreeNode.

2

Add the target sum variable

Create a variable called targetSum and set it to 22.

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(5,
    new TreeNode(4,
        new TreeNode(11,
            new TreeNode(7),
            new TreeNode(2)
        )
    ),
    new TreeNode(8,
        new TreeNode(13),
        new TreeNode(4,
            null,
            new TreeNode(1)
        )
    )
);

// Create targetSum variable and set to 22
// Your code here

Hint

Simply create a constant variable named targetSum and assign it the value 22.

3

Write the hasPathSum function

Write a function called hasPathSum that takes parameters root of type TreeNode | null and sum of type number. The function should return true if there is a root-to-leaf path where the sum of node values equals sum, otherwise false. Use recursion and check if the current node is a leaf and if the remaining sum equals the node's value. Use exact function name and parameter names.

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(5,
    new TreeNode(4,
        new TreeNode(11,
            new TreeNode(7),
            new TreeNode(2)
        )
    ),
    new TreeNode(8,
        new TreeNode(13),
        new TreeNode(4,
            null,
            new TreeNode(1)
        )
    )
);

const targetSum = 22;

// Write hasPathSum function below
// Your code here

Hint

Use recursion to check if the current node is null (return false), if it is a leaf (check if sum equals node value), otherwise call hasPathSum on left and right children with updated sum.

4

Print the result of hasPathSum

Write a console.log statement to print the result of calling hasPathSum with root and targetSum.

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(5,
    new TreeNode(4,
        new TreeNode(11,
            new TreeNode(7),
            new TreeNode(2)
        )
    ),
    new TreeNode(8,
        new TreeNode(13),
        new TreeNode(4,
            null,
            new TreeNode(1)
        )
    )
);

const targetSum = 22;

function hasPathSum(root: TreeNode | null, sum: number): boolean {
    if (root === null) {
        return false;
    }
    if (root.left === null && root.right === null) {
        return sum === root.val;
    }
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

// Print the result of hasPathSum with root and targetSum
// Your code here

Hint

Use console.log(hasPathSum(root, targetSum)) to print the result.