Katkat
Back

Count Target-Sum Paths in an N-ary Tree

ByteDanceSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to navigate tree structures and use hash maps to track cumulative path sums efficiently, specifically in the context of an N-ary tree.

Problem Statement

Given the root of an N-ary tree and an integer targetSum, count the number of paths that sum up to targetSum. A path is defined as a sequence of nodes from any node to any descendant node along the tree edges. Unlike a binary tree, each node in this N-ary tree can have a list of children.

Input Structure

Each node in the tree is defined as:

class Node:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children is not None else []

Constraints

  • The number of nodes in the tree is in the range [0, 10^4].
  • Node values are between -1000 and 1000.
  • targetSum is between -10^7 and 10^7.

Example

Consider a tree where the root has value 5, with two children: 3 and 2. If targetSum is 8, a path exists from the root (5) to the child (3).

# Input: root = Node(5, [Node(3), Node(2)]), targetSum = 8
# Output: 1

Implementation

Implement the following function:

def countPaths(root: 'Node', targetSum: int) -> int:
    pass

Considerations

  • Can paths start at the root and end at any node? Yes.
  • Can paths start at any node and end at any of its descendants? Yes.
  • What happens if the tree is empty?
  • Ensure the time complexity is better than O(N^2) where N is the number of nodes.

Hints

Hint 1

Use a prefix sum approach: the sum of a path between node A and node B is equal to the root-to-B prefix sum minus the root-to-A-parent prefix sum.

Hint 2

Maintain a hash map during a depth-first search that stores the frequency of all prefix sums encountered from the root to the current node.

Hint 3

Remember to remove the current node's prefix sum from the hash map as you backtrack to ensure it doesn't affect other branches of the tree.

Follow-up questions

  • How would you modify your solution if paths were strictly required to start at the root and end at a leaf?
  • What is the space complexity of your solution, and can you optimize it for very deep, skewed trees?
  • How would the algorithm change if node values could be modified dynamically during the traversal?