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

Path Sum Root to Leaf in Binary Tree

📖 Scenario: Imagine you have a family tree where each person has a number representing their age. You want to check if there is a path from the oldest ancestor (root) down to a youngest family member (leaf) where the sum of ages equals a specific number.

🎯 Goal: Build a simple binary tree and write a function to check if there is a root-to-leaf path with a given sum.

📋 What You'll Learn

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

Create a binary tree with exact nodes and values as specified

Create a variable called targetSum with the exact value specified

Write a function called hasPathSum that takes root and targetSum and returns true or false

Print the result of calling hasPathSum(root, targetSum)

💡 Why This Matters

🌍 Real World

Checking paths in trees is useful in decision-making systems, network routing, and family tree analysis.

💼 Career

Understanding tree traversal and recursion is important for software engineering roles involving data structures and algorithms.

1

Create the Binary Tree Node Class and Tree

Create a class called TreeNode with a constructor that takes val, left, and right parameters. Then create the binary tree with root node value 5, left child 4, right child 8, left child of 4 is 11, and left and right children of 11 are 7 and 2. The right child 8 has left child 13 and right child 4, and the right child 4 has right child 1. Store the root node in a variable called root.

DSA Javascript

// Your code here

Hint

Define the TreeNode class first, then build the tree from bottom to top using new TreeNode.

2

Set the Target Sum

Create a variable called targetSum and set it to 22.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = 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)
    )
  )
);

// Your code here

Hint

Just create a variable targetSum and assign it the number 22.

3

Write the hasPathSum Function

Write a function called hasPathSum that takes parameters root and targetSum. It should return true if there is a root-to-leaf path in the tree where the sum of node values equals targetSum, otherwise false. Use recursion and check if the current node is null, if it is a leaf, and subtract the node value from targetSum as you go down.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = 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;

// Your code here

Hint

Use recursion to check if the current node is a leaf and if the remaining sum equals the node's value. Otherwise, subtract the node's value and check left and right children.

4

Print the Result

Print the result of calling hasPathSum(root, targetSum).

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = 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, targetSum) {
  if (root === null) return false;
  if (root.left === null && root.right === null) {
    return root.val === targetSum;
  }
  const newSum = targetSum - root.val;
  return hasPathSum(root.left, newSum) || hasPathSum(root.right, newSum);
}

// Your code here

Hint

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

Practice

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

easy

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

B. The maximum depth of the binary tree

C. The total number of nodes in the binary tree

D. The sum of all node values in 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 a given target sum.

2. Step 2: Differentiate from other tree properties

   This is different from finding depth, counting nodes, or summing all nodes. It specifically checks for 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 A

4. Quick Check:

   Path sum problem = Check root-to-leaf sum [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 root-to-leaf
• Ignoring leaf node condition

2. Which of the following is the correct base case check in JavaScript for a null node in a recursive path sum function?

easy

A. if (node === null) return true;

B. if (node == undefined) return true;

C. if (node === undefined) return null;

D. if (node === null) return false;

Solution

1. Step 1: Identify base case for recursion

   When the current node is null, it means no path exists here, so return false to indicate failure to find the path.

2. Step 2: Check JavaScript strict equality and return value

   Using 'node === null' is correct to check null nodes, and returning false means no valid path found.

3. Final Answer:

   if (node === null) return false; -> Option D

4. Quick Check:

   Null node means no path = false [OK]

Hint: Return false on null node to stop recursion [OK]

Common Mistakes:

• Returning true on null node
• Using == instead of ===
• Returning null instead of boolean

3. What will be the output of the following code snippet?

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

function hasPathSum(node, sum) {
  if (node === null) return false;
  if (!node.left && !node.right) return sum === node.val;
  return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

const root = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))), new TreeNode(8, null, new TreeNode(4, null, new TreeNode(1))));
console.log(hasPathSum(root, 22));

medium

A. true

B. false

C. undefined

D. TypeError

Solution

1. Step 1: Trace the path sums in the tree

   Check if any root-to-leaf path sums to 22. The path 5->4->11->2 sums to 22 (5+4+11+2=22).

2. Step 2: Evaluate the recursive calls

   The function returns true because the path exists, so console.log prints true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Path 5-4-11-2 sum=22 = true [OK]

Hint: Check leaf paths sums carefully to confirm true [OK]

Common Mistakes:

• Ignoring leaf node condition
• Miscomputing sum along path
• Assuming false when path exists

4. Find the bug in this JavaScript function for path sum and select the fix:

function hasPathSum(node, sum) {
  if (node === null) return false;
  if (!node.left && !node.right) return sum = node.val;
  return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

medium

A. Change 'node === null' to 'node == null' in base case

B. Remove the leaf node check entirely

C. Change 'sum = node.val' to 'sum === node.val' in the leaf check

D. Change '||' to '&&' in the return statement

Solution

1. Step 1: Identify incorrect assignment in leaf check

   The line 'return sum = node.val;' uses assignment '=' instead of comparison '===' which causes wrong behavior.

2. Step 2: Correct the comparison operator

   Replace '=' with '===' to properly check if sum equals node.val at leaf nodes.

3. Final Answer:

   Change 'sum = node.val' to 'sum === node.val' in the leaf check -> Option C

4. Quick Check:

   Use '===' for comparison, not '=' [OK]

Hint: Use '===' for equality checks, not '=' assignment [OK]

Common Mistakes:

• Using '=' instead of '===' in conditions
• Removing necessary base cases
• Changing logical operators incorrectly

5. Given a binary tree where node values can be negative, which modification is necessary to correctly check for a path sum equal to target?

function hasPathSum(node, sum) {
  if (node === null) return false;
  if (!node.left && !node.right) return sum === node.val;
  return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

hard

A. Use absolute values of node.val and sum in comparisons

B. No change needed; current code works with negative values

C. Change base case to return true if sum <= node.val

D. Add a visited set to avoid infinite loops with negative values

Solution

1. Step 1: Understand negative values impact

   The current recursive approach subtracts node values from sum and checks leaf equality, which works even if values are negative.

2. Step 2: Confirm no cycles in binary tree

   Binary trees have no cycles, so no infinite loops occur; no visited set needed.

3. Final Answer:

   No change needed; current code works with negative values -> Option B

4. Quick Check:

   Negative values handled by subtraction correctly [OK]

Hint: Binary trees have no cycles; negative values handled naturally [OK]

Common Mistakes:

• Adding unnecessary visited sets
• Changing base case incorrectly
• Using absolute values which breaks logic