Frontend School

Sibling Sum Path

DSA
medium

Sibling Sum Path

Medium
Tree
DFS
Binary Tree
Path Sum

Overview

In Postman, complex workflows or API dependency graphs can often be modeled as tree structures. Imagine a scenario where a primary API request (root) triggers several downstream services (children). Sometimes, the cumulative 'cost' or 'resource consumption' along a specific execution path needs to consider not just the service itself, but also parallel, critical services that might be invoked at the same level. This problem challenges you to determine if a specific 'resource budget' can be met by following a complete workflow path, accounting for both the primary service and its immediate peer services.

What you need to do / Task

Implement the hasSiblingSumPath function which determines if there is a root-to-leaf path in a binary tree such that the sum of the node values along that path, plus the values of any immediate siblings of those path nodes, equals a given targetSum.

Definition of Sibling Sum

For each node N on a root-to-leaf path:

  1. Add N.val to the current path sum.
  2. If N has an immediate sibling S (i.e., N and S share the same parent), add S.val to the current path sum.
    • The root node has no parent and thus no siblings.

Input & output

Input:

  • root: The root of a binary tree. Each TreeNode object has an integer val, a left child (which is either a TreeNode or null), and a right child (which is either a TreeNode or null).
  • targetSum: An integer representing the target sum.

Output:

  • boolean: true if such a root-to-leaf path exists, false otherwise.

Clarifications

  • An empty tree (root = null) should return false.
  • Node values can be positive, negative, or zero.
  • A node without siblings (e.g., the root, or a child whose parent only has one child) contributes only its own value to the sibling sum at its level.
  • The path must be strictly from the root to a leaf node.

Examples

1

Example 1

Input:

root = [1,2,3], targetSum = 6

Output:

true

Note:

Path 1 -> 2:

  • Node 1 (root): val=1. No sibling. Current sum = 1.
  • Node 2: val=2. Sibling=3. Current sum = 1 + 2 + 3 = 6. (Leaf) Since 6 == targetSum, return true.
2

Example 2

Input:

root = [1,2,null,4], targetSum = 7

Output:

true

Note:

Path 1 -> 2 -> 4:

  • Node 1 (root): val=1. No sibling. Current sum = 1.
  • Node 2: val=2. No sibling (since 1.right is null). Current sum = 1 + 2 = 3.
  • Node 4: val=4. No sibling (since 2.right is null). Current sum = 3 + 4 = 7. (Leaf) Since 7 == targetSum, return true.
3

Example 3

Input:

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output:

false

Note:

Let's trace a path, e.g., 5 -> 4 -> 11 -> 7:

  • Node 5 (root): val=5. No sibling. Current sum = 5.
  • Node 4: val=4. Sibling=8. Current sum = 5 + 4 + 8 = 17.
  • Node 11: val=11. No sibling. Current sum = 17 + 11 = 28.
  • Node 7: val=7. Sibling=2. Current sum = 28 + 7 + 2 = 37. (Leaf) 37 != 22. All other root-to-leaf paths also do not sum up to 22 following the sibling sum logic.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -10^9 <= targetSum <= 10^9

Out of scope

  • Modifying the tree structure.
  • Handling non-integer node values or malformed TreeNode objects.

What interviewers evaluate

  • Correctness of the algorithm for all edge cases (e.g., empty tree, single node, skewed trees).
  • Efficiency of the solution in terms of time and space complexity.
  • Clarity, readability, and maintainability of the code.
  • Ability to articulate the thought process, justify design choices, and discuss potential optimizations.

Loading editor...