[Leetcode] 1448번: Count Good Nodes in Binary Tree

https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/

intial

It is good path if the nodes in the path so far have values greater than the current node. Like if root is 3 and its left is 4, it is good path. But if it is like 3->4->1 , 1 isnt good node.

my initial solution was like

class Solution:
    def __init__(self):
        self.ans = 1  # Use instance variable instead of nonlocal
    def goodNodes(self, root: TreeNode) -> int:
        if root.left is None:
            return 
        elif root.right is None:
            return
        if root.left.val>=root.val:
            self.ans+=1
        if root.right.val>=root.val:
            self.ans+=1   
        self.goodNodes(root.left)
        self.goodNodes(root.right)
        return self.ans

But look at these

        if root.left is None:
            return 
        elif root.right is None:
            return

If we are on a node and its left is None but it has a right node, we still wanna traverse that right node. But these if statements return right away if root.left is None. So it is incorrect.

Instead we should consider the recursion as the root node itself and set the if statement onto the root node.

        if root is None:
            return

solution

with changing given method parameters like maxVal value

class Solution:
    def __init__(self):
        self.ans = 0  # Use instance variable instead of nonlocal
    def goodNodes(self, root: TreeNode, maxVal=-int(10e18)) -> int:
        if root is None:
            return
        if root.val>=maxVal:
            self.ans+=1
            maxVal = root.val
        self.goodNodes(root.left,maxVal)
        self.goodNodes(root.right,maxVal)
        return self.ans

with helper function

class Solution:
    def __init__(self):
        self.ans = 0  # Instance variable to store count

    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_so_far):
            if not node:
                return
            
            # If current node is greater or equal to max seen so far, count it
            if node.val >= max_so_far:
                self.ans += 1
                max_so_far = node.val  # Update max value for the path

            # Debugging output
            print(f"Visiting Node: {node.val}, Max So Far: {max_so_far}, Good Nodes Count: {self.ans}")

            # Recur for left and right subtree
            dfs(node.left, max_so_far)
            dfs(node.right, max_so_far)

        dfs(root, float('-inf'))  # Start DFS from the root with -infinity as the initial max
        return self.ans  # Return the final count

complexity

time: o(n)

Best case (balanced tree): O(log N) space
Worst case (skewed tree): O(N) space
Why log N? If it is balanced, the recursion stack depends on the height of the tree.