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.

Practice

1. What does the "Path Sum Root to Leaf" problem ask you to find in a binary tree?

easy

A. The sum of all node values in the binary tree

B. If there exists a root-to-leaf path with a sum equal to a given target

C. The total number of nodes in the binary tree

D. The maximum depth of the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if there is any path from the root node down to any leaf node where the sum of the node values equals the target sum.

2. Step 2: Differentiate from other tree properties

   It is not about depth, total nodes, or sum of all nodes, but specifically about a path sum from root to leaf.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option B

4. Quick Check:

   Path sum means root-to-leaf sum = D [OK]

Hint: Focus on root-to-leaf paths, not entire tree sums [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not just root-to-leaf
• Ignoring leaf node condition

2. Which of the following TypeScript function signatures correctly represents a function to check path sum in a binary tree node defined as class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }?

easy

A. function hasPathSum(root: number, sum: TreeNode): boolean

B. function hasPathSum(root: TreeNode, sum: string): boolean

C. function hasPathSum(root: TreeNode | null, sum: number): boolean

D. function hasPathSum(root: TreeNode | null): number

Solution

1. Step 1: Check parameter types

   The root should be a TreeNode or null (empty tree), and sum should be a number representing the target sum.

2. Step 2: Check return type

   The function returns a boolean indicating if such a path exists.

3. Final Answer:

   function hasPathSum(root: TreeNode | null, sum: number): boolean -> Option C

4. Quick Check:

   Correct types and return boolean = B [OK]

Hint: Root can be null; sum is number; return boolean [OK]

Common Mistakes:

• Swapping parameter types
• Using wrong return type
• Missing null for root parameter

3. Given the following binary tree and target sum = 22, what will the function hasPathSum(root, 22) return?

    5
   / \
  4   8
 /   / \
11  13  4
/  \      
7    2     1

medium

A. null

B. false

C. SyntaxError

D. true

Solution

1. Step 1: Identify root-to-leaf paths and their sums

   Check paths: 5->4->11->7 = 27, 5->4->11->2 = 22, 5->8->13 = 26, 5->8->4->1 = 18.

2. Step 2: Check if any path sum equals 22

   Path 5->4->11->2 sums to 22, so function returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Path sum 22 exists = true [OK]

Hint: Sum each root-to-leaf path, check for target [OK]

Common Mistakes:

• Ignoring leaf node condition
• Calculating sum incorrectly
• Confusing partial paths with full root-to-leaf

4. Consider this TypeScript code snippet for checking path sum:

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

What does the function return if the tree is empty (root = null) and sum is 0?

medium

A. Returns false for empty tree and sum 0

B. Causes infinite recursion

C. Throws runtime error due to null access

D. Returns true incorrectly for non-empty tree

Solution

1. Step 1: Analyze base case for empty tree

   When root is null, if (!root) returns false immediately.

2. Step 2: Confirm for sum = 0

   Empty tree has no root-to-leaf path regardless of target sum, so false is correct.

3. Final Answer:

   Returns false for empty tree and sum 0 -> Option A

4. Quick Check:

   Null root always returns false [OK]

Hint: Empty tree always returns false [OK]

Common Mistakes:

• Thinking empty tree with sum 0 should return true
• Expecting runtime error without null check
• Confusing empty tree with single-node tree

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which approach best solves this problem?

hard

A. Use DFS to track current path and sum, collect paths when sum matches at leaf

B. Use BFS and stop at first matching path

C. Use a queue to store sums only, ignoring paths

D. Return true or false immediately when sum matches any node

Solution

1. Step 1: Understand requirement to collect all matching paths

   We need to find all root-to-leaf paths whose sums equal the target, not just check existence.

2. Step 2: Choose traversal and tracking method

   DFS (depth-first search) allows tracking the current path and sum, and collecting paths when leaf and sum match.

3. Step 3: Evaluate other options

   BFS is less natural for path tracking; queues without paths lose information; returning boolean stops early.

4. Final Answer:

   Use DFS to track current path and sum, collect paths when sum matches at leaf -> Option A

5. Quick Check:

   DFS with path tracking = A [OK]

Hint: Track path and sum with DFS to collect all matching paths [OK]

Common Mistakes:

• Using BFS without path tracking
• Stopping at first match instead of collecting all
• Ignoring leaf node condition