Leetcode 1448. Count Good Nodes in Binary Tree

Problem Description

In this problem, we are given a binary tree where each node contains a value. We need to find all such nodes, that in the path from the root to the node, there are no nodes with a value greater than the current node. These nodes are considered "good". Our task is to return the total number of such "good" nodes in the given binary tree.

For example,

Suppose we have a binary tree like this:

1
2
3      3
4     / \
5    1   4
6   /   / \
7  3   1   5

The good nodes are:

• Node 3 (the root node)
• Node 4: The path is 3 -> 4, and 4 is the maximum.
• Node 5: The path is 3 -> 4 -> 5, and 5 is the maximum.
• Node 3: The path is 3 -> 1 -> 3, and 3 is the maximum.

Hence, the output will be 4.

Approach

The solution to this problem is straightforward using Depth-First Search (DFS). We initialize a variable maxi with the minimum possible integer value.

For each visited node in the tree, we update maxi to have the maximum value between the maxi and the value of the current node. Plus one to the count of goodNodes if the current node is a good node, i.e., if the value is more than or equal to maxi.

Recurse this process for the left and the right child of each node to make sure all nodes get checked for "good" condition.

C++ Solution

1
2 cpp
3class Solution {
4 public:
5  int goodNodes(TreeNode* root, int maxi = INT_MIN) {
6    if (root == nullptr)
7      return 0;
8    const int newMax = max(maxi, root->val);
9    return (root->val >= maxi)
10           + goodNodes(root->left, newMax)
11           + goodNodes(root->right, newMax);
12  }
13};

Python Solution

1
2 python
3class Solution:
4    def goodNodes(self, root: TreeNode, maxi: int = float('-inf')) -> int:
5        if root is None:
6            return 0
7        newMax = max(maxi, root.val)
8        return (root.val >= maxi) + self.goodNodes(root.left, newMax) + self.goodNodes(root.right, newMax)

Java Solution

1
2 java
3class Solution {
4    int goodNodes(TreeNode root, int maxi) {
5        if (root == null)
6            return 0;
7        int newMax = Math.max(maxi, root.val);
8        return (root.val >= maxi ? 1 : 0) + goodNodes(root.left, newMax) + goodNodes(root.right, newMax);
9    }
10    
11    public int goodNodes(TreeNode root) {
12        return goodNodes(root, Integer.MIN_VALUE);
13    }
14}

JavaScript Solution

1
2 javascript
3var goodNodes = function(root, maxi = Number.MIN_SAFE_INTEGER) {
4    if (!root)
5        return 0;
6    let newMax = Math.max(maxi, root.val);
7    return (root.val >= maxi ? 1 : 0) + goodNodes(root.left, newMax) + goodNodes(root.right, newMax);
8};

C# Solution

1
2 csharp
3public class Solution {
4    private int GoodNodes(TreeNode root, int maxi) {
5        if (root == null)
6            return 0;
7        int newMax = Math.Max(maxi, root.val);
8        return (root.val >= maxi ? 1 : 0) + GoodNodes(root.left, newMax) + GoodNodes(root.right, newMax);
9    }
10    
11    public int GoodNodes(TreeNode root) {
12        return GoodNodes(root, int.MinValue);
13    }
14}

Above solutions implement a DFS approach with a time complexity of O(n), since we visit each node of the binary tree exactly once. The space complexity is O(h), where h is the height of the binary tree, as that is the maximum depth of the recursive call stack during the DFS.## Optimization While the above solutions are correct and efficient enough for all but the largest binary trees, they can be further optimized by avoiding the use of recursion and instead employing an iterative depth-first search (DFS) strategy using a stack.

This iterative approach will drastically reduce the space complexity from O(h) to O(1), as we only need to store the maximum value so far, making it a more feasible solution for large trees.

Here's how we could implement this solution in Python:

1
2python
3class Solution:
4    def goodNodes(self, root: TreeNode) -> int:
5        stack = [(root, root.val)]
6        good_nodes = 0
7        while stack:
8            node, maxi = stack.pop()
9            if node.val >= maxi:
10                good_nodes += 1
11            maxi = max(maxi, node.val)
12            if node.left:
13                stack.append((node.left, maxi))
14            if node.right:
15                stack.append((node.right, maxi))
16        return good_nodes

And here's the Java version of the same solution:

1
2java
3class Solution {
4    public int goodNodes(TreeNode root) {
5        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
6        stack.push(new Pair(root, root.val));
7        int goodNodes = 0;
8        while(!stack.isEmpty()) {
9            Pair<TreeNode, Integer> pair = stack.pop();
10            TreeNode node = pair.getKey();
11            int maxi = pair.getValue();
12            if(node.val >= maxi) {
13                goodNodes++;
14            }
15            maxi = Math.max(maxi, node.val);
16            if(node.left != null) {
17                stack.push(new Pair(node.left, maxi));
18            }
19            if(node.right != null) {
20                stack.push(new Pair(node.right, maxi));
21            }
22        }
23        return goodNodes;
24    }
25}

In JavaScript:

1
2javascript
3const goodNodes = (root) => {
4    let stack = [[root, root.val]];
5    let goodNodes = 0;
6    while (stack.length > 0) {
7        let [node, maxi] = stack.pop();
8        if (node.val >= maxi) {
9            goodNodes++;
10        }
11        maxi = Math.max(maxi, node.val);
12        if (node.left) {
13            stack.push([node.left, maxi]);
14        }
15        if (node.right) {
16            stack.push([node.right, maxi]);
17        }
18    }
19    return goodNodes;
20}

This improved solution maintains the O(n) time complexity, as we still need to visit each node once. However, the space complexity is now O(1), making it a more efficient solution especially for large binary trees. This optimization demonstrates how iterative algorithms are often more efficient than their recursive counterparts.