We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Nodes with Even-Valued Grandparent

Number: 1243

Difficulty: Medium

Paid? No

Companies: Salesforce, Meta, Amazon

Problem Description

Given the root of a binary tree, return the sum of values of nodes that have an even-valued grandparent. A grandparent of a node is the parent of its parent (if it exists). If no such nodes exist, return 0.

Key Insights

  • Use a DFS (depth-first search) traversal to visit every node.
  • Pass along the parent and grandparent values during the recursion.
  • Check if the current node's grandparent exists and has an even value; if so, add the current node's value to the sum.
  • Each node is visited exactly once, ensuring a linear time solution.
  • The recursion tracks the state with additional parameters without extra data structures.

Space and Time Complexity

Time Complexity: O(n) – each of the n nodes is processed once.
Space Complexity: O(h) – where h is the height of the tree, representing the maximum depth of the recursion stack.

Solution

We can solve this problem by performing a DFS traversal on the binary tree. The DFS helper function is designed to receive the current node along with its parent and grandparent values. If the grandparent exists and has an even value, then the current node’s value is added to the cumulative sum. We then recursively continue the same process for both the left and right children, updating the parent and grandparent accordingly. This approach efficiently computes the required sum without needing extra auxiliary data structures beyond the recursion stack.

Code Solutions

Below are code solutions with line-by-line comments in Python, JavaScript, C++, and Java.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # Value of the node
        self.left = left  # Left child
        self.right = right  # Right child

def sumEvenGrandparent(root):
    # DFS helper function that carries the current node, its parent, and grandparent values.
    def dfs(node, parent, grandparent):
        if not node:
            return 0  # Base case: if the node is None, simply return 0.
        total = 0
        # If the grandparent exists and is even, add the current node's value.
        if grandparent is not None and grandparent % 2 == 0:
            total += node.val
        # Recursively call dfs for left and right subtrees, updating parent and grandparent.
        total += dfs(node.left, node.val, parent)
        total += dfs(node.right, node.val, parent)
        return total

    return dfs(root, None, None)
← Back to All Questions