Jobs

Interviews

Discussions

Path Sum IV

Medium

Asked by:

38 views

Topics:

ArraysTrees

You are given a binary tree represented by a list of positive 3-digit integers. Each integer is of the form abc, where the hundreds digit a represents the depth of the node (starting from 1), the tens digit b represents the position of the node in the level (starting from 1), and the units digit c is the value of the node.

For example, the input [113, 215, 221] represents the following tree:

   3
  / \
 5   1

You are asked to find the sum of all the paths from the root to the leaves.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation: 
The tree is:
    3
   / \
  5   1
The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221]
Output: 4
Explanation: 
The tree is:
    3
     \
      1
The path sum is (3 + 1) = 4.

Constraints:

The number of nodes in the tree is in the range [1, 15].
100 <= node <= 999
Every number in the list represents a node in the tree.

Try coding it in LeetCode

Path Sum IV

Medium

Asked by:

38 views

Topics:

ArraysTrees

For example, the input [113, 215, 221] represents the following tree:

   3
  / \
 5   1

You are asked to find the sum of all the paths from the root to the leaves.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation: 
The tree is:
    3
   / \
  5   1
The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221]
Output: 4
Explanation: 
The tree is:
    3
     \
      1
The path sum is (3 + 1) = 4.

Constraints:

The number of nodes in the tree is in the range [1, 15].
100 <= node <= 999
Every number in the list represents a node in the tree.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the digits? For example, is the depth (first digit) always at least 1, and can the value (third digit) be zero?
Is the input guaranteed to represent a valid, connected binary tree starting from a root at depth 1, or could it be disjointed or have gaps (e.g., a child node without a parent)?
What is the expected behavior for an empty input array or an array that only contains a single node?
Could the encoded positions create an invalid structure, such as two nodes occupying the same position (e.g., `115` and `116`)? If so, how should that be handled?
A 'leaf' is typically a node with no children. Should I consider a node a leaf only if both its potential child positions are unoccupied, or is it defined differently in this context?

Brute Force Solution

Approach

The brute force approach is to first rebuild the entire tree structure from the special three-digit numbers provided. Then, we'll trace every single path from the very top of the tree down to each of its end points, or leaves, adding up the values along each path as we go.

Here's how the algorithm would work step-by-step:

First, take the list of three-digit numbers and mentally arrange them into a tree shape. Each number tells you its depth, its position on that level, and its value, so you can figure out where each node goes and what its value is.
Once the tree is built, start at the very top node, which is the root.
From the root, explore the path going to its left child. Keep a running total of the values of the nodes you've visited on this path.
Continue down this left-side path until you reach a node that has no more children below it—this is a 'leaf' node.
When you hit a leaf, add the path's total sum to a grand total for all paths.
Now, backtrack and do the same thing for the right child of the root, and continue this process for every single branch in the tree.
You must trace every possible route from the root all the way down to every single leaf node.
After you've explored all the paths and added up their individual sums, the final grand total is your answer.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def pathSum(nums):
    nodes = {}
    for number in nums:
        depth = number // 100
        position = (number // 10) % 10
        value = number % 10
        nodes[(depth, position)] = TreeNode(value)

    # Reconstruct the tree by linking parent nodes to their children based on their positions.
    for depth, position in nodes:
        if depth < 4:
            parent_node = nodes.get((depth, position))
            left_child_key = (depth + 1, 2 * position - 1)
            right_child_key = (depth + 1, 2 * position)
            if left_child_key in nodes:
                parent_node.left = nodes[left_child_key]
            if right_child_key in nodes:
                parent_node.right = nodes[right_child_key]

    # The root of the tree is always at depth 1, position 1.
    if not (1, 1) in nodes:
        return 0
    
    root_node = nodes[(1, 1)]
    grand_total_of_all_path_sums = [0]

    def depth_first_search_on_paths(current_node, current_path_sum):
        if not current_node:
            return
        
        new_path_sum = current_path_sum + current_node.value

        # A leaf node has no children; its path sum must be added to the grand total.
        if not current_node.left and not current_node.right:
            grand_total_of_all_path_sums[0] += new_path_sum
            return
        
        depth_first_search_on_paths(current_node.left, new_path_sum)
        depth_first_search_on_paths(current_node.right, new_path_sum)

    # Start the traversal from the root with an initial sum of 0.
    depth_first_search_on_paths(root_node, 0)
    return grand_total_of_all_path_sums[0]

Big(O) Analysis

Time Complexity

O(n) – The time complexity is O(n), where n is the number of nodes in the input list. First, we iterate through the n numbers to build the tree, which takes O(n) time. Then, we perform a single traversal of the entire tree, visiting each of the n nodes exactly once to calculate the path sums. Since building the tree and traversing it are sequential operations, the total time complexity is dominated by these linear scans, resulting in O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The primary space cost comes from rebuilding the tree structure from the input numbers. This involves creating a data structure, like a hash map or an array, to store the nodes of the tree. Since there are N numbers in the input list, we need to store N nodes, leading to space usage proportional to N. Additionally, the recursive traversal from the root to the leaves uses stack space, and in the worst case (a skewed tree), the recursion depth could be N, also contributing O(N) space.

Optimal Solution

Approach

The problem gives us a list of numbers representing a tree, but it's jumbled. The most efficient strategy is to first rebuild the tree structure in a more familiar way, like a map. Then, we can travel down every path from the root to a leaf, summing up the values as we go, and add all these path sums together for the final answer.

Here's how the algorithm would work step-by-step:

First, we need to organize the given numbers so we can easily find any node in the tree. A good way to do this is to create a lookup table where each node's position (its depth and placement) points to its value.
With our tree organized, we can start at the very top, the root node.
From the current node, we'll explore downwards, keeping a running total of the values we've seen on the path from the root so far.
When we're at a node, we check if it has any children below it. To find potential children, we look at the next level down, one position to the left and one to the right.
If a node has no children (it's a 'leaf'), it means we've reached the end of a path. We add the running total for this complete path to our final grand total.
If a node does have children, we continue this process for each child, passing along the updated running total.
We repeat this exploration for every branch until we have visited every single leaf node and added its complete path sum to our grand total.
The final result is the sum of all the individual path sums we've calculated.

Code Implementation

class Solution:
    def pathSum(self, nums: list[int]) -> int:
        self.total_path_sum = 0
        node_values_by_position = {number // 10: number % 10 for number in nums}

        def traverse_paths(node_position_key, current_path_sum):
            if node_position_key not in node_values_by_position:
                return

            node_value = node_values_by_position[node_position_key]
            current_path_sum += node_value

            depth = node_position_key // 10
            position_in_level = node_position_key % 10

            # Calculate positions for potential left and right children in the next level.
            left_child_key = (depth + 1) * 10 + (2 * position_in_level - 1)
            right_child_key = (depth + 1) * 10 + (2 * position_in_level)

            # A node is a leaf if it has no children; its path sum must be added to the total.
            is_leaf_node = left_child_key not in node_values_by_position and right_child_key not in node_values_by_position
            if is_leaf_node:
                self.total_path_sum += current_path_sum
                return
            
            # We must recursively explore both child paths to ensure all paths are summed.
            traverse_paths(left_child_key, current_path_sum)
            traverse_paths(right_child_key, current_path_sum)
        
        # The traversal must start from the root node, which is always at position 11 (depth 1, pos 1).
        traverse_paths(11, 0)
        return self.total_path_sum

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by two main operations. First, we iterate through the input list of n nodes to build a map for efficient lookups, which takes O(n) time. Next, we traverse the tree structure represented by this map, visiting each of the n nodes exactly once to calculate path sums. Since building the map and traversing the tree are sequential operations, the total complexity is driven by the number of nodes, resulting in a linear time complexity of O(n).

Space Complexity

O(N) – The primary auxiliary space is used for the lookup table, as described in step 1, to store the tree structure. This table, likely a hash map, will hold N key-value pairs, where N is the number of nodes in the input list. Additionally, the recursive exploration described in steps 3-7 requires a call stack, and in the worst-case scenario of a skewed tree, the depth of this stack could also be proportional to N. Therefore, the dominant space complexity is driven by the lookup table, resulting in O(N) auxiliary space.

Edge Cases

Case	How to Handle
Empty input array `nums`	The path sum is zero, so the function should return 0 immediately.
A single-node tree (input array has one element)	This single node is both the root and a leaf, so its value is the total path sum.
A disconnected tree structure (e.g., a node's parent is missing)	Since the root (depth 1, position 1) must exist, this case is impossible under problem constraints.
A tree that is just a single path (a stick)	The algorithm correctly calculates the single path sum by traversing down to the one leaf node.
Node values are zero	The path sum calculation works correctly as adding zero does not change the running totals.
A perfect, complete, or full binary tree	The solution correctly sums the paths to all leaves, regardless of the tree's shape.
The input array `nums` is not sorted by node encoding	A hash map approach is robust to the input order as it directly maps depth and position to value.
Maximum possible tree size and values leading to a large total sum	The total sum could exceed a standard 32-bit integer, so a 64-bit integer type should be used for the accumulator.

Empty input array `nums`

How to Handle:

The path sum is zero, so the function should return 0 immediately.

A single-node tree (input array has one element)

How to Handle:

This single node is both the root and a leaf, so its value is the total path sum.

A disconnected tree structure (e.g., a node's parent is missing)

How to Handle:

Since the root (depth 1, position 1) must exist, this case is impossible under problem constraints.

A tree that is just a single path (a stick)

How to Handle:

The algorithm correctly calculates the single path sum by traversing down to the one leaf node.

Node values are zero

How to Handle:

The path sum calculation works correctly as adding zero does not change the running totals.

A perfect, complete, or full binary tree

How to Handle:

The solution correctly sums the paths to all leaves, regardless of the tree's shape.

The input array `nums` is not sorted by node encoding

How to Handle:

A hash map approach is robust to the input order as it directly maps depth and position to value.

Maximum possible tree size and values leading to a large total sum

How to Handle:

The total sum could exceed a standard 32-bit integer, so a 64-bit integer type should be used for the accumulator.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the digits? For example, is the depth (first digit) always at least 1, and can the value (third digit) be zero?
Is the input guaranteed to represent a valid, connected binary tree starting from a root at depth 1, or could it be disjointed or have gaps (e.g., a child node without a parent)?
What is the expected behavior for an empty input array or an array that only contains a single node?
Could the encoded positions create an invalid structure, such as two nodes occupying the same position (e.g., `115` and `116`)? If so, how should that be handled?
A 'leaf' is typically a node with no children. Should I consider a node a leaf only if both its potential child positions are unoccupied, or is it defined differently in this context?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take the list of three-digit numbers and mentally arrange them into a tree shape. Each number tells you its depth, its position on that level, and its value, so you can figure out where each node goes and what its value is.
Once the tree is built, start at the very top node, which is the root.
From the root, explore the path going to its left child. Keep a running total of the values of the nodes you've visited on this path.
Continue down this left-side path until you reach a node that has no more children below it—this is a 'leaf' node.
When you hit a leaf, add the path's total sum to a grand total for all paths.
Now, backtrack and do the same thing for the right child of the root, and continue this process for every single branch in the tree.
You must trace every possible route from the root all the way down to every single leaf node.
After you've explored all the paths and added up their individual sums, the final grand total is your answer.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def pathSum(nums):
    nodes = {}
    for number in nums:
        depth = number // 100
        position = (number // 10) % 10
        value = number % 10
        nodes[(depth, position)] = TreeNode(value)

    # Reconstruct the tree by linking parent nodes to their children based on their positions.
    for depth, position in nodes:
        if depth < 4:
            parent_node = nodes.get((depth, position))
            left_child_key = (depth + 1, 2 * position - 1)
            right_child_key = (depth + 1, 2 * position)
            if left_child_key in nodes:
                parent_node.left = nodes[left_child_key]
            if right_child_key in nodes:
                parent_node.right = nodes[right_child_key]

    # The root of the tree is always at depth 1, position 1.
    if not (1, 1) in nodes:
        return 0
    
    root_node = nodes[(1, 1)]
    grand_total_of_all_path_sums = [0]

    def depth_first_search_on_paths(current_node, current_path_sum):
        if not current_node:
            return
        
        new_path_sum = current_path_sum + current_node.value

        # A leaf node has no children; its path sum must be added to the grand total.
        if not current_node.left and not current_node.right:
            grand_total_of_all_path_sums[0] += new_path_sum
            return
        
        depth_first_search_on_paths(current_node.left, new_path_sum)
        depth_first_search_on_paths(current_node.right, new_path_sum)

    # Start the traversal from the root with an initial sum of 0.
    depth_first_search_on_paths(root_node, 0)
    return grand_total_of_all_path_sums[0]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need to organize the given numbers so we can easily find any node in the tree. A good way to do this is to create a lookup table where each node's position (its depth and placement) points to its value.
With our tree organized, we can start at the very top, the root node.
From the current node, we'll explore downwards, keeping a running total of the values we've seen on the path from the root so far.
When we're at a node, we check if it has any children below it. To find potential children, we look at the next level down, one position to the left and one to the right.
If a node has no children (it's a 'leaf'), it means we've reached the end of a path. We add the running total for this complete path to our final grand total.
If a node does have children, we continue this process for each child, passing along the updated running total.
We repeat this exploration for every branch until we have visited every single leaf node and added its complete path sum to our grand total.
The final result is the sum of all the individual path sums we've calculated.

Code Implementation

class Solution:
    def pathSum(self, nums: list[int]) -> int:
        self.total_path_sum = 0
        node_values_by_position = {number // 10: number % 10 for number in nums}

        def traverse_paths(node_position_key, current_path_sum):
            if node_position_key not in node_values_by_position:
                return

            node_value = node_values_by_position[node_position_key]
            current_path_sum += node_value

            depth = node_position_key // 10
            position_in_level = node_position_key % 10

            # Calculate positions for potential left and right children in the next level.
            left_child_key = (depth + 1) * 10 + (2 * position_in_level - 1)
            right_child_key = (depth + 1) * 10 + (2 * position_in_level)

            # A node is a leaf if it has no children; its path sum must be added to the total.
            is_leaf_node = left_child_key not in node_values_by_position and right_child_key not in node_values_by_position
            if is_leaf_node:
                self.total_path_sum += current_path_sum
                return
            
            # We must recursively explore both child paths to ensure all paths are summed.
            traverse_paths(left_child_key, current_path_sum)
            traverse_paths(right_child_key, current_path_sum)
        
        # The traversal must start from the root node, which is always at position 11 (depth 1, pos 1).
        traverse_paths(11, 0)
        return self.total_path_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array `nums`	The path sum is zero, so the function should return 0 immediately.
A single-node tree (input array has one element)	This single node is both the root and a leaf, so its value is the total path sum.
A disconnected tree structure (e.g., a node's parent is missing)	Since the root (depth 1, position 1) must exist, this case is impossible under problem constraints.
A tree that is just a single path (a stick)	The algorithm correctly calculates the single path sum by traversing down to the one leaf node.
Node values are zero	The path sum calculation works correctly as adding zero does not change the running totals.
A perfect, complete, or full binary tree	The solution correctly sums the paths to all leaves, regardless of the tree's shape.
The input array `nums` is not sorted by node encoding	A hash map approach is robust to the input order as it directly maps depth and position to value.
Maximum possible tree size and values leading to a large total sum	The total sum could exceed a standard 32-bit integer, so a 64-bit integer type should be used for the accumulator.

Empty input array `nums`

How to Handle:

The path sum is zero, so the function should return 0 immediately.

A single-node tree (input array has one element)

How to Handle:

This single node is both the root and a leaf, so its value is the total path sum.

A disconnected tree structure (e.g., a node's parent is missing)

How to Handle:

Since the root (depth 1, position 1) must exist, this case is impossible under problem constraints.

A tree that is just a single path (a stick)

How to Handle:

The algorithm correctly calculates the single path sum by traversing down to the one leaf node.

Node values are zero

How to Handle:

The path sum calculation works correctly as adding zero does not change the running totals.

A perfect, complete, or full binary tree

How to Handle:

The solution correctly sums the paths to all leaves, regardless of the tree's shape.

The input array `nums` is not sorted by node encoding

How to Handle:

A hash map approach is robust to the input order as it directly maps depth and position to value.

Maximum possible tree size and values leading to a large total sum

How to Handle:

The total sum could exceed a standard 32-bit integer, so a 64-bit integer type should be used for the accumulator.