#1315

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Sum of Nodes with Even-Valued Grandparent

This problem involves calculating the sum of nodes with an even-valued grandparent in a binary tree.

tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a binary tree. The task is to return the sum of values of the nodes with an even-valued grandparent. If no nodes have an even-valued grandparent, return 0. A grandparent of a node is defined as the parent of its parent, if it exists.

To solve this, you need to efficiently traverse the tree while keeping track of both the parent and grandparent nodes. During traversal, sum the node values when the grandparent has an even value. The traversal can be done using depth-first or breadth-first search techniques.

Examples

Example 1

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Output: 18

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

Example details omitted.

Constraints

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

Solution Approach

Tree Traversal with State Tracking

Start by traversing the tree, keeping track of the current node, its parent, and its grandparent. For each node, check if the grandparent has an even value, and if so, add the current node's value to the sum.

Depth-First Search (DFS)

DFS is a natural choice for this problem as it allows you to explore each node while maintaining the state of parent and grandparent. Use recursion to move down the tree while passing state information along the way.

Breadth-First Search (BFS)

Alternatively, use BFS for an iterative approach. Track parent and grandparent nodes as you traverse level by level. This method can be more suitable for certain tree structures but still requires careful state management.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity of this solution is O(N), where N is the number of nodes in the tree. This is because each node is visited exactly once. The space complexity is also O(N) due to the need to store state information for each node during traversal, especially for DFS when recursion is used, or for BFS when the queue stores nodes.

What Interviewers Usually Probe

Ability to keep track of state while traversing the tree.
Efficient use of tree traversal techniques, either DFS or BFS.
Clear understanding of parent-child relationships and their role in tree traversal.

Common Pitfalls or Variants

Common pitfalls

Failing to properly maintain the state of parent and grandparent nodes during traversal.
Not considering edge cases such as a tree with only one node or no even-valued grandparents.
Using a non-optimal tree traversal technique that leads to unnecessary complexity or memory usage.

Follow-up variants

Modify the problem to sum nodes with odd-valued grandparents.
Add a constraint that the tree is balanced or sorted in some way.
Consider different tree types, such as AVL or Red-Black trees, and adapt the traversal accordingly.

FAQ

How do I handle state tracking in the 'Sum of Nodes with Even-Valued Grandparent' problem?

Maintain the current node, its parent, and its grandparent during the tree traversal. This ensures that the sum is only calculated when the grandparent is even.

What traversal method should I use for 'Sum of Nodes with Even-Valued Grandparent'?

Both DFS and BFS are suitable. DFS is often more straightforward for recursive approaches, while BFS can be useful for iterative traversal.

What are the time and space complexities for this problem?

The time complexity is O(N), and the space complexity is also O(N) due to the need to store information about the parent and grandparent during traversal.

Can I solve this problem using iterative methods?

Yes, you can use BFS for an iterative approach, where the state of parent and grandparent is tracked at each level of traversal.

Are there edge cases I should consider for this problem?

Yes, consider cases such as a tree with only one node or a tree where no nodes have an even-valued grandparent.

terminal

Solution

Solution 1: DFS

We design a function $dfs(root, x)$, which represents the sum of the values of the nodes that meet the conditions in the subtree with $root$ as the root node and $x$ as the value of the parent node of $root$. The answer is $dfs(root, 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, x: int) -> int:
            if root is None:
                return 0
            ans = dfs(root.left, root.val) + dfs(root.right, root.val)
            if x % 2 == 0:
                if root.left:
                    ans += root.left.val
                if root.right:
                    ans += root.right.val
            return ans

        return dfs(root, 1)

Continue Practicing

#1302 deepest leaves sum #1361 validate binary tree nodes #1261 find elements in a contaminated binary tree