Jobs

Interviews

Discussions

Sum of Nodes with Even-Valued Grandparent

Medium

Asked by:

More companies

20 views

Topics:

TreesRecursion

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Example 2:

Input: root = [1]
Output: 0

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
1 <= Node.val <= 100

Try coding it in LeetCode

Sum of Nodes with Even-Valued Grandparent

Medium

Asked by:

20 views

Topics:

TreesRecursion

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Example 2:

Input: root = [1]
Output: 0

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
1 <= Node.val <= 100

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 is the range of values for the node values in the binary tree? Can they be negative, zero, or floating-point numbers?
Can the tree be empty (root is null)? If so, what should I return in that case?
Are there any specific constraints on the structure of the tree, such as being balanced or complete?
By 'grandparent', do you strictly mean two levels above the current node, or can we assume a node is its own ancestor?
If a node has multiple grandparents with even values, should I count the node's value multiple times in the sum?

Brute Force Solution

Approach

We need to find the sum of the values of nodes that have a grandparent with an even value. The brute-force method involves checking every node in the tree to see if it meets the condition by exploring its ancestors.

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

Start at the very top of the tree, the root node.
For each node in the tree, check if it has a grandparent.
To do this, look at the node's parent, and then at that parent's parent.
If a grandparent exists, check if the grandparent's value is an even number.
If the grandparent's value is even, then add the current node's value to a running total.
Do this for every single node in the tree.
After checking every node, the final running total will be the answer.

Code Implementation

def sum_of_even_grandparent_brute_force(root):
    total_sum = 0

    def traverse(node):
        nonlocal total_sum

        if not node:
            return

        # Check if the current node has a grandparent with an even value.
        if node.parent and node.parent.parent:

            grandparent = node.parent.parent
            if grandparent.val % 2 == 0:

                # Add the current node's value to the running total.
                total_sum += node.val

        # Recursively traverse the left and right subtrees.
        traverse(node.left)
        traverse(node.right)

    # Begin the traversal from the root.
    traverse(root)

    return total_sum

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once. For each node, it performs a constant amount of work to check for the existence and value of its grandparent. Since the amount of work per node is constant, and we visit each of the n nodes once, the time complexity is directly proportional to the number of nodes, resulting in O(n) time complexity.

Space Complexity

O(N) – The provided plain English explanation suggests a full traversal of the tree. While the explanation doesn't explicitly mention a recursive or iterative implementation, to visit every node (as suggested by steps 1-7), one common approach is using Depth-First Search (DFS) via recursion or Breadth-First Search (BFS) using a queue. If a recursive DFS approach is chosen, the recursion stack could grow up to the height of the tree in the worst-case scenario (a skewed tree), where N is the number of nodes. Therefore, the auxiliary space required for the recursion stack is O(N) in the worst case. No other significant auxiliary space appears to be used according to the plain English explanation.

Optimal Solution

Approach

We'll traverse the tree while keeping track of grandparent nodes. The key is to look two levels up from each node. If a grandparent exists and has an even value, we add the current node's value to a running total.

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

Start at the very top of the tree.
For each node we visit, check if its grandparent exists and if that grandparent's value is an even number.
If the grandparent exists and is even, add the current node's value to our running total.
Continue this process for every node in the entire tree.
The final running total represents the sum of all nodes with even-valued grandparents.

Code Implementation

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

def sum_even_grandparent(root):
    total_sum = 0

    def dfs(node, parent, grandparent):
        nonlocal total_sum

        if not node:
            return

        # Check if grandparent exists and its value is even
        if grandparent and grandparent.val % 2 == 0:
            total_sum += node.val

        # Traverse the left subtree
        dfs(node.left, node, parent)

        # Traverse the right subtree
        dfs(node.right, node, parent)

    # Initiate DFS traversal with None for parent and grandparent
    dfs(root, None, None)

    return total_sum

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a traversal of the binary tree, visiting each node exactly once. For each node visited, a constant amount of work is done: checking if the grandparent exists and if its value is even. Since the number of nodes visited is proportional to the size of the tree, which we can represent as n, the time complexity is O(n).

Space Complexity

O(H) – The algorithm performs a tree traversal, and the dominant factor in space complexity is the recursion stack. In the worst-case scenario (a skewed tree), the recursion depth can be equal to the height (H) of the tree. Thus, the maximum number of function calls on the call stack would be proportional to the height of the tree. Therefore, the auxiliary space complexity is O(H), where H is the height of the tree, which in the worst case, is O(N) where N is the number of nodes.

Edge Cases

Case	How to Handle
Null root	Return 0 immediately as there are no nodes to process.
Single node tree	Return 0, as a single node cannot have a grandparent.
Two node tree (root and one child)	Return 0, as neither node can have a grandparent.
Grandparent with an even value has only one child	The algorithm should correctly check for the existence of both left and right grandchildren even if only one exists.
Grandparent with an even value has grandchildren with negative values.	The algorithm should correctly handle negative node values when calculating the sum.
Tree with a deep and highly unbalanced structure.	The recursive approach should handle unbalanced trees without stack overflow errors, or an iterative approach should be favored.
Large integer values in the nodes leading to integer overflow during summation.	Use a data type that can accommodate large sums, such as long.
Tree with many nodes where most grandparent values are even.	The solution should iterate efficiently through the tree without unnecessary computations.

Null root

How to Handle:

Return 0 immediately as there are no nodes to process.

Single node tree

How to Handle:

Return 0, as a single node cannot have a grandparent.

Two node tree (root and one child)

How to Handle:

Return 0, as neither node can have a grandparent.

Grandparent with an even value has only one child

How to Handle:

The algorithm should correctly check for the existence of both left and right grandchildren even if only one exists.

Grandparent with an even value has grandchildren with negative values.

How to Handle:

The algorithm should correctly handle negative node values when calculating the sum.

Tree with a deep and highly unbalanced structure.

How to Handle:

The recursive approach should handle unbalanced trees without stack overflow errors, or an iterative approach should be favored.

Large integer values in the nodes leading to integer overflow during summation.

How to Handle:

Use a data type that can accommodate large sums, such as long.

Tree with many nodes where most grandparent values are even.

How to Handle:

The solution should iterate efficiently through the tree without unnecessary computations.

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 is the range of values for the node values in the binary tree? Can they be negative, zero, or floating-point numbers?
Can the tree be empty (root is null)? If so, what should I return in that case?
Are there any specific constraints on the structure of the tree, such as being balanced or complete?
By 'grandparent', do you strictly mean two levels above the current node, or can we assume a node is its own ancestor?
If a node has multiple grandparents with even values, should I count the node's value multiple times in the sum?

Brute Force Solution

Approach

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

Start at the very top of the tree, the root node.
For each node in the tree, check if it has a grandparent.
To do this, look at the node's parent, and then at that parent's parent.
If a grandparent exists, check if the grandparent's value is an even number.
If the grandparent's value is even, then add the current node's value to a running total.
Do this for every single node in the tree.
After checking every node, the final running total will be the answer.

Code Implementation

def sum_of_even_grandparent_brute_force(root):
    total_sum = 0

    def traverse(node):
        nonlocal total_sum

        if not node:
            return

        # Check if the current node has a grandparent with an even value.
        if node.parent and node.parent.parent:

            grandparent = node.parent.parent
            if grandparent.val % 2 == 0:

                # Add the current node's value to the running total.
                total_sum += node.val

        # Recursively traverse the left and right subtrees.
        traverse(node.left)
        traverse(node.right)

    # Begin the traversal from the root.
    traverse(root)

    return total_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the very top of the tree.
For each node we visit, check if its grandparent exists and if that grandparent's value is an even number.
If the grandparent exists and is even, add the current node's value to our running total.
Continue this process for every node in the entire tree.
The final running total represents the sum of all nodes with even-valued grandparents.

Code Implementation

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

def sum_even_grandparent(root):
    total_sum = 0

    def dfs(node, parent, grandparent):
        nonlocal total_sum

        if not node:
            return

        # Check if grandparent exists and its value is even
        if grandparent and grandparent.val % 2 == 0:
            total_sum += node.val

        # Traverse the left subtree
        dfs(node.left, node, parent)

        # Traverse the right subtree
        dfs(node.right, node, parent)

    # Initiate DFS traversal with None for parent and grandparent
    dfs(root, None, None)

    return total_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root	Return 0 immediately as there are no nodes to process.
Single node tree	Return 0, as a single node cannot have a grandparent.
Two node tree (root and one child)	Return 0, as neither node can have a grandparent.
Grandparent with an even value has only one child	The algorithm should correctly check for the existence of both left and right grandchildren even if only one exists.
Grandparent with an even value has grandchildren with negative values.	The algorithm should correctly handle negative node values when calculating the sum.
Tree with a deep and highly unbalanced structure.	The recursive approach should handle unbalanced trees without stack overflow errors, or an iterative approach should be favored.
Large integer values in the nodes leading to integer overflow during summation.	Use a data type that can accommodate large sums, such as long.
Tree with many nodes where most grandparent values are even.	The solution should iterate efficiently through the tree without unnecessary computations.

Null root

How to Handle:

Return 0 immediately as there are no nodes to process.

Single node tree

How to Handle:

Return 0, as a single node cannot have a grandparent.

Two node tree (root and one child)

How to Handle:

Return 0, as neither node can have a grandparent.

Grandparent with an even value has only one child

How to Handle:

The algorithm should correctly check for the existence of both left and right grandchildren even if only one exists.

Grandparent with an even value has grandchildren with negative values.

How to Handle:

The algorithm should correctly handle negative node values when calculating the sum.

Tree with a deep and highly unbalanced structure.

How to Handle:

The recursive approach should handle unbalanced trees without stack overflow errors, or an iterative approach should be favored.

Large integer values in the nodes leading to integer overflow during summation.

How to Handle:

Use a data type that can accommodate large sums, such as long.

Tree with many nodes where most grandparent values are even.

How to Handle:

The solution should iterate efficiently through the tree without unnecessary computations.