Problem statement

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

Solution

In this problem we need to traverse tree and find all nodes which have all ancestors less or equal than given node. Let us traverse our tree and change its nodes, such that in each node we will keep the biggest value on path node -> .. -> root.

  1. We update self.count if child.val >= root.val, that is node child is good.
  2. We update value for child, in this case when we run recursion for this node, we know the biggest value on the path between this node and root.
  3. Finally, we run recursion for every children.

Complexity

It is just O(n) for time and O(h) for additional space, because we use recursion.

Code

class Solution:
    def __init__(self):
        self.count = 0

    def goodNodes(self, root):
        for child in filter(None, [root.left, root.right]):
            self.count += child.val >= root.val
            child.val = max(child.val, root.val)
            self.goodNodes(child)
  
        return self.count + 1