Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
 
Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
 
Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node's value is between [-10^4, 10^4].

Difficulty: interview

Starter code:

# 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 goodNodes(self, root: TreeNode) -> int:
        

Solutions:
# 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 goodNodes(self, root: TreeNode) -> int:
        self.cnt=0
        def helper(root,maxm):
            if not root:
                return
            if root.val>=maxm:
                self.cnt+=1
                maxm=root.val
            if root.left:
                helper(root.left,maxm)
            if root.right:
                helper(root.right,maxm)
        maxm=root.val
        helper(root,maxm)
        return self.cnt

# 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 preorder(self, root, max_so_far, ctr):
        if not root:
            return
        if root.val>=max_so_far:
            max_so_far = root.val
            ctr[0] += 1
        self.preorder(root.left, max_so_far, ctr)
        self.preorder(root.right, max_so_far, ctr)
        
    def goodNodes(self, root: TreeNode) -> int:
        max_so_far = -111111111111111
        ctr = [0]
        self.preorder(root, max_so_far, ctr)
        return ctr[0]
        


# 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 helper_rec(self,root,tempMax):
        if root is None:
            return
        
        if root.val >= tempMax:
            self.count += 1
            tempMax=max(root.val,tempMax)
        self.helper_rec(root.left,tempMax)
        self.helper_rec(root.right, tempMax)

    def goodNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        #self.tempMax=0
        self.count=0
        self.helper_rec(root,root.val)
        return self.count

# 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 goodNodes(self, root: TreeNode) -> int:
        #preorder traverse, keeping track of the max for that path
        #if X is >= the max on the path, numGoodNodes += 1
        
        stack = [(root, root.val)]
        count = 0
        
        while stack:
            cur, greatest = stack.pop()
            if cur:
                if cur.val >= greatest:
                    count += 1

                if cur.right:
                    stack.append((cur.right, max(cur.right.val, greatest)))
                if cur.left:
                    stack.append((cur.left, max(cur.left.val, greatest)))
                       
        return count

                       

                       


        
        


# 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:
    '''
    - as we traverse down, we measure the maxSoFar and compare current 
    node with that
    - current node is good if >= maxSoFar, so count as one
    - can traverse recursively
    '''
    def goodNodes(self, root: TreeNode) -> int:
        def traverse(node, maxSoFar=float(\"-inf\")):
            # check base case (null node)
            if not node:
                return 0
            
            # process node
            count = 1 if node.val >= maxSoFar else 0
            maxSoFar = max(maxSoFar, node.val)
            
            # traverse children, adding count along the way
            return traverse(node.left, maxSoFar) + traverse(node.right, maxSoFar) + count
            
        return traverse(root)
        
        

# 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 traverse(self, root, currentMax):
        if root != None:
            if currentMax <= root.val:
                self.count += 1
            self.traverse(root.left, max(currentMax, root.val))
            self.traverse(root.right, max(currentMax, root.val))
    
    def goodNodes(self, root: TreeNode) -> int:
        self.count = 0
        self.traverse(root, float('-inf'));
        return self.count


# 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 goodNodes(self, root: TreeNode) -> int:
        res = [0]
        
        def dfs(node, m):
            if not node: return
            if node.val >= m:
                res[0] += 1
                
            dfs(node.left, max(node.val, m))
            dfs(node.right, max(node.val, m))
            
        dfs(root, root.val)
        return res[0]
                
            


# 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 goodNodes(self, root: TreeNode, m = -10**4) -> int:
        
        return (self.goodNodes(root.left, max(m, root.val))+self.goodNodes(root.right, max(m, root.val))+(root.val>=m)) if root else 0
    
           
        


# 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 goodNodes(self, root: TreeNode) -> int:
        
        
        def helper(root, max_sofar):
            
            if not root:
                return 0
            
            total = 0
            if root.val >= max_sofar:
                total += 1
                
            total += helper(root.left, max(max_sofar, root.val))
            total += helper(root.right, max(max_sofar, root.val))
            
            return total
        
        return helper(root, float(\"-inf\"))

# 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 goodNodes(self, root: TreeNode) -> int:
        res = 0
        q = collections.deque([(root, root.val)])
        while q:
            node, cur_max = q.popleft()
            if node.val >= cur_max:
                res += 1
            for child in filter(bool, (node.left, node.right)):
                q.append((child, max(child.val, cur_max)))
        return res

# 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 __init__(self):
        self.total_count = 0
        
    def goodNodes(self, root: TreeNode) -> int:
        return self.goodNodesHelper(root, [])
        
    def goodNodesHelper(self, root, max_first_stack):
        if not root:
            return 
        elif max_first_stack == []:
            max_first_stack.append(root.val)
            self.total_count += 1

        elif max_first_stack[0] <= root.val:
            max_first_stack = [root.val] + max_first_stack 
            self.total_count += 1
        else:
            max_first_stack = max_first_stack + [root.val]
        self.goodNodesHelper(root.left, max_first_stack)
        self.goodNodesHelper(root.right, max_first_stack)
        return self.total_count

# 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 goodNodes(self, root: TreeNode) -> int:
        if root == None:
            return 0
        self.count = 0
        self._goodNodes(root, root.val)
        return self.count
        
    def _goodNodes(self, curNode, curGreatest):
        if curNode == None:
            return
        if curNode.val >= curGreatest:
            self.count += 1
        
        self._goodNodes(curNode.left, max(curNode.val, curGreatest))
        self._goodNodes(curNode.right, max(curNode.val, curGreatest))

# 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 goodNodes(self, root: TreeNode) -> int:
        self.ans = 0
        self.traverse(root, root.val)
        return self.ans
    
    def traverse(self, root, so_far):
        if root:
            if root.val >= so_far:
                self.ans += 1
                so_far = root.val
            self.traverse(root.left, so_far)
            self.traverse(root.right, so_far)


# 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 goodNodes(self, root: TreeNode) -> int:
        self.count = 0
        self.dfs(root, float('-inf'))
        return self.count
    
    def dfs(self, root, parent):
        if not root:
            return 0
        
        if root.val >= parent:
            self.count += 1
        
        l = self.dfs(root.left, max(root.val, parent))

        r = self.dfs(root.right, max(root.val, parent))
        
        return l+r
            
                
                
            
            
        


# 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 goodNodes(self, root: TreeNode) -> int:
        sumNode = []
        self.goodNode(root, -234627, sumNode)
        return len(sumNode)
    
    def goodNode(self, root, maxSoFar, sumNode):
        if root is None:
            return
        
        #print(\"MaxSoFar\", maxSoFar)
        #print(\"Root val\", root.val)
        print((root.val))
        
        if root.val >= maxSoFar:
            #print(\"Added\", root.val)
            sumNode.append(root.val)
            #print(sumNode)
        
        maxSoFarNow = max(maxSoFar, root.val)
        
        self.goodNode(root.left, maxSoFarNow, sumNode)
        self.goodNode(root.right, maxSoFarNow, sumNode)
        
        
        
        
        

        


# 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 goodNodes(self, root: TreeNode) -> int:
        res=[]
        cnt=0
        def dfs(node):
            nonlocal cnt
            res.append(node.val)
            if res[-1]==max(res):
                cnt+=1
            if node.left:
                dfs(node.left)
            if node.right:
                dfs(node.right)
            if res:
                res.pop()
        dfs(root)
        return cnt

# 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 goodNodes(self, root: TreeNode) -> int:
        self.ans = 0
        def tra(node, maxtillnow):
            if node:
                if node.val>=maxtillnow:
                    self.ans +=1
                tra(node.left, max(maxtillnow, node.val))
                tra(node.right, max(maxtillnow, node.val))
            
            
        tra(root, float('-inf'))
        
        return self.ans

# 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 goodNodes(self, root: TreeNode) -> int:
        self.count=0
        def helper(root,maxVal):
            if root is None:
                return 
            if root.val>=maxVal:
                maxVal=root.val
                self.count+=1
            helper(root.left,maxVal)
            helper(root.right,maxVal)
        helper(root,root.val)
        return self.count


# 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 traverse(self, node, max_val):
        if node.val >= max_val:
            self.traverse_count += 1
        max_val = max(max_val, node.val)
        if node.left: self.traverse(node.left, max_val)
        if node.right: self.traverse(node.right, max_val)

    def goodNodes(self, root: TreeNode) -> int:
        if root:
            self.traverse_count = 0
            self.traverse(root, float('-inf'))
            return self.traverse_count
        return 0

# 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 goodNodes(self, root: TreeNode) -> int:
        count = 0
        def dfs(node,prevVal):
            nonlocal count
            if node:
                maxPrev = max(node.val,prevVal)
                if node.val >= prevVal:
                    count += 1
                dfs(node.left,maxPrev)
                dfs(node.right,maxPrev)
        dfs(root,root.val)
        return count

# 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 goodNodes(self, root: TreeNode) -> int:
        self.count=0
        def helper(root,maxVal):
            if root is None:
                return 
            if root.val>=maxVal:
                maxVal=root.val
                self.count+=1
            helper(root.left,maxVal)
            helper(root.right,maxVal)
        helper(root,-11111)
        return self.count
#     def dfs(root, max_till_now):
#             if not root:
#                 return
            
#             if root.val >= max_till_now:
#                 max_till_now = root.val
#                 self.good_nodes += 1
                
#             dfs(root.left, max_till_now)
#             dfs(root.right, max_till_now)
        
#         dfs(root,-10001)
#         return self.good_nodes


# 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 goodNodes(self, root: TreeNode) -> int:
        
        int_min = -10000000
        ans = self.solve(root, int_min)
        return ans
        
    def solve(self, root: TreeNode, int_min: int) -> int:
        
        if(root==None):
            return 0
        if(root.val < int_min):
             return self.solve(root.left, int_min) + self.solve(root.right, int_min)
        else:
             return self.solve(root.left, root.val) + self.solve(root.right, root.val)+1


# 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:
    count=0
    def goodNodes(self, root: TreeNode) -> int:
        current=root.val
        
        path=[]
        path.append(float('-inf'))
        \"\"\" append min val in to path and check if root val gretaer or == to max(path) if true increase count by 1 and add root to path.
        recursively call root.left and root.right and pop the top element)\"\"\"
        def good(path,root):
            if root is None:
                return
            if root.val>=max(path):
                self.count=self.count+1
            path.append(root.val)
                #print(root.val)
            good(path,root.right)
            good(path,root.left)
            path.pop()
            return self.count
        #print(self.count)
        return good(path,root)
            
                          
            
                    
                          
            
        

# 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 goodNodes(self, root: TreeNode) -> int:
        return self.count_good_nodes(root, root.val)
    
    def count_good_nodes(self, root: TreeNode, highest_val: int) -> int:
        current_highest = highest_val
        total = 0
        
        if root.val >= current_highest:
            total += 1
            current_highest = root.val

        if root.left:
            total += self.count_good_nodes(root.left, current_highest)
        if root.right:
            total += self.count_good_nodes(root.right, current_highest)
        
        return total

# 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 goodNodes(self, root: TreeNode) -> int:
        
        if root is None:
            return 0
        
        out = [0]
        #maxValue = -float('inf')
        
        def _recHelper(curr,maxValue):
            if curr is None:
                return
            
            if curr.val >= maxValue:
                out[0] += 1
            
            _recHelper(curr.left, max(curr.val, maxValue))
            _recHelper(curr.right, max(curr.val, maxValue))
        
        _recHelper(root, -float('inf'))
        
        return out[0]
    


# 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 goodNodes(self, root: TreeNode) -> int:
        def traverse(n, maxval):
            if not n: return 0
            visible = 1 if n.val >= maxval else 0
            maxval = max(maxval, n.val)
            return traverse(n.left, maxval) + visible + traverse(n.right, maxval)
        
        return traverse(root, float(\"-inf\"))
            
            

# 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 goodNodes(self, root: TreeNode) -> int:
        
        
        def dfs(node,m):
            if node==None:
                return 0
            value =1 if node.val>=m else 0
            m=max(m,node.val)
            return dfs(node.right,m)+dfs(node.left,m)+value
        return dfs(root,-float(inf))

# 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 goodNodes(self, root: TreeNode) -> int:
        self.count=0
        def helper(root,maxVal):
            if root is None:
                return 
            if root.val>=maxVal:
                maxVal=root.val
                self.count+=1
            helper(root.left,maxVal)
            helper(root.right,maxVal)
        helper(root,-10001)
        return self.count
#     def dfs(root, max_till_now):
#             if not root:
#                 return
            
#             if root.val >= max_till_now:
#                 max_till_now = root.val
#                 self.good_nodes += 1
                
#             dfs(root.left, max_till_now)
#             dfs(root.right, max_till_now)
        
#         dfs(root,-10001)
#         return self.good_nodes


# 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 goodNodes(self, root: TreeNode) -> int:
        result = 0
        def findNodes(root, path):
            nonlocal result
            if not root:
                return
            path = [*path, root.val] 
            if max(path) <= root.val:
                result += 1
            findNodes(root.left, path)
            findNodes(root.right, path) 
        findNodes(root, [])
        return result


# 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 goodNodes(self, root: TreeNode) -> int:
        def c(r,v):
            if not r:
                return 0
            mx = max(r.val,v)
            
            return (r.val >= mx) + c(r.left,mx) + c(r.right,mx)
        
        return c(root,root.val)

# 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 goodNodes(self, root: TreeNode) -> int:
        return self.dfs(root, 0, float('-inf'))
    
    def dfs(self, root, good, max_val): 
        if root == None: 
            return good 
        if root.val >= max_val: 
            good += 1 
            max_val = root.val 
        good = self.dfs(root.left, good, max_val)
        good = self.dfs(root.right, good, max_val)
        return good
        


# 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 goodNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
       
        self.count = 0
        self.dfs(root, root.val)
        return self.count
    def dfs(self, root, max_num):
        if root is None:
            return
        if root.val >= max_num:
            max_num = root.val
            self.count += 1
        self.dfs(root.left, max_num)
        self.dfs(root.right, max_num)

# 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 _goodNodes(self, root: TreeNode, maxSeen: int) -> int:
        print(f\"Node: {root.val}\")
        if not root:
            print(\"return 0\")
            return 0
        this = 1 if root.val >= maxSeen else 0
        left = 0
        right = 0
        if root.left:
            left = self._goodNodes(root.left, max(root.val, maxSeen))
        
        # right
        if root.right:
            right = self._goodNodes(root.right, max(root.val, maxSeen))
        
        return this + left + right
    
    def goodNodes(self, root: TreeNode) -> int:
        return self._goodNodes(root, root.val)

# 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 goodNodes(self, root: TreeNode) -> int:
        queue = collections.deque()
        queue.append([root,-float('inf')])
        count = 0
        while queue:
            node, pVal = queue.popleft()
            if node.val >= pVal:
                count += 1
                if node.left:
                    queue.append([node.left, node.val])
                if node.right:
                    queue.append([node.right, node.val])
            else:
                if node.left:
                    queue.append([node.left, pVal])
                if node.right:
                    queue.append([node.right, pVal])
        return count
            


# 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 goodNodes(self, root: TreeNode) -> int:
        \"\"\"
        
        beat 19.91%
        wrong idea --> count # of nodes >= root.val. This is my first try..
        
        create a path from root to current node.
        
        a good node if all the nodes in the path are smaller than the current node
        
        this is a good example:
        [2,null,4,10,8,null,null,4]
        
        \"\"\"
        
        # the root nodes is always good node
        # so it start from 1
        self.numGoodNodes = 1
        def dfsVisit(node, path):
            if node is None:
                return
            
            if path and node.val >= max(path):
                self.numGoodNodes += 1 
                
            dfsVisit(node.left, path + [node.val])
            dfsVisit(node.right, path + [node.val])
        
        dfsVisit(root, [])
                
        return self.numGoodNodes

#     def goodNodes(self, root: TreeNode) -> int:
#         \"\"\"
#         instead of keep the whole path, keep only the maxVal in the path
#         \"\"\"
        
#         # the root nodes is always good node
#         # so it start from 1
#         self.numGoodNodes = 1
#         def dfsVisit(node, maxVal):
#             if node is None:
#                 return
            
#             if node.val >= max(path):
#                 self.numGoodNodes += 1 
                
#             dfsVisit(node.left, path + [node.val])
#             dfsVisit(node.right, path + [node.val])
        
#         dfsVisit(root, [])
                
#         return self.numGoodNodes

# 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 goodNodes(self, root: TreeNode) -> int:
        \"\"\"
        count # of nodes >= root.val
        
        create a path from root to current node.
        
        a good node if all the nodes in the path are smaller than the current node
        
        this is a good example:
        [2,null,4,10,8,null,null,4]
        
        \"\"\"
        
        # the root nodes is always good node
        # so it start from 1
        self.numGoodNodes = 1
        def dfsVisit(node, path):
            if node is None:
                return
            
            if len(path) > 0 and node.val >= max(path):
                self.numGoodNodes += 1 
                
            dfsVisit(node.left, path + [node.val])
            dfsVisit(node.right, path + [node.val])
        
        dfsVisit(root, [])
                
        return self.numGoodNodes

# 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 goodNodes(self, root: TreeNode) -> int:
        
#         def traverse(node: TreeNode, good_threshold: int) -> int:
#             good_threshold = max(good_threshold, node.val)
            
#             left_count = right_count = 0
            
#             if node.left is not None:
#                 left_count = traverse(node.left, good_threshold)
                
#             if node.right is not None:
#                 right_count = traverse(node.right, good_threshold)
            
#             return left_count + right_count + (1 if good_threshold <= node.val else 0)
        
#         good_count = traverse(root, -10e4)
        
#         return good_count
        queue = deque()
        TraverseItem = namedtuple('TraverseItem', ['threshold', 'node'])
        queue.append(TraverseItem(threshold=-10e4, node=root))
        
        good_count = 0
        
        while len(queue) != 0:
            n = queue.pop()
            
            threshold = max(n.node.val, n.threshold)
            
            if n.node.left is not None:
                queue.append(TraverseItem(threshold=threshold, node=n.node.left))
            
            if n.node.right is not None:
                queue.append(TraverseItem(threshold=threshold, node=n.node.right))
                
            if threshold <= n.node.val :
                good_count = good_count + 1
        
        return good_count

# 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 goodNodes(self, root: TreeNode) -> int:
   
        count = 0 
        
        def rootToNode(root,path):
            
            nonlocal count
            
            if root is None:
                return
            
            path.append(root.val)
     
            if(max(path) == root.val):
                count +=1
                    
                    
            rootToNode(root.left,path.copy())
            rootToNode(root.right,path.copy())
            
        rootToNode(root,[])
        
        return count
            
            


# 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 goodNodes(self, root: TreeNode) -> int:
        def check(node,val):
            if not node:
                return 0
            if node.val>=val:
                return 1 + check(node.left,node.val) + check(node.right,node.val)
            return check(node.left,val) + check(node.right,val)
        return check(root,root.val)

# 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

def order(root, maxi):
    if root is None:
        return 0
    
    count = 0
    if root.val >= maxi:
        count += 1
        maxi = root.val
        
    return count + order(root.left, maxi) + order(root.right, maxi)
    

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        return order(root, root.val)

# 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 goodNodes(self, root: TreeNode) -> int:
        def helper(root: TreeNode, maxVal: int, count: List[int]):
            if not root:
                return
            else:
                if root.val >= maxVal:
                    count[0] += 1
    
                helper(root.left, max(maxVal, root.val), count) 
                helper(root.right, max(maxVal, root.val), count)
    
        count = [0]
        helper(root, -math.inf, count)
        return count[0]

# 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 __init__(self):
        self.res=0
    def goodNodes(self, root: TreeNode) -> int:
        
        def add(l, n):
            nl = l.copy()
            nl.append(n)
            return nl
            
        
        self.res=0
        def traverse(node, path):
            
            if node is None:
                return
            
            if(node.val>=max(path)):
                self.res+=1
                
            traverse(node.left, add(path, node.val))
            traverse(node.right, add(path, node.val))
            
            
            
        traverse(root, [-float('inf')])
        return self.res

# 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 traverse(self, node, max_val):
        if node.val >= max_val:
            self.traverse_count += 1
        max_val = max(max_val, node.val)
        if node.left: self.traverse(node.left, max_val)
        if node.right: self.traverse(node.right, max_val)

    def goodNodes(self, root: TreeNode) -> int:
        self.traverse_count = 0
        if root: self.traverse(root, float('-inf'))
        return self.traverse_count

# 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 goodNodes(self, root: TreeNode) -> int:
        
        visited = set()
        
        def countNode(node: TreeNode, maxVal: int) -> int:
            if not node:
                return 0
            
            if node.val >= maxVal:
                return 1 + countNode(node.left, node.val) + countNode(node.right, node.val)
            else:
                return 0 + countNode(node.left, maxVal) + countNode(node.right, maxVal)
            
        return countNode(root, root.val)

# 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 goodNodes(self, root: TreeNode) -> int:
        self.result = 0
        self.check_node(root, root.val)
        return self.result
        
    def check_node(self, node, max_value):
        if node.val >= max_value:
            self.result += 1
        max_value = max(max_value, node.val)
        if node.left != None:
            self.check_node(node.left, max_value)
        if node.right != None:
            self.check_node(node.right, max_value)


# 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 goodNodes(self, root: TreeNode) -> int:
        def helper(root, max_val):
            if not root:
                return 0
        
            ans=0
            if root.val >= max_val:
                max_val=root.val
                ans+=1
            return ans+helper(root.left, max_val)+helper(root.right, max_val)
        return helper(root, -float('inf'))
            


# 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 goodNodes(self, root: TreeNode) -> int:
        traverse_count = 0
        def traverse(node, max_val):
            nonlocal traverse_count
            if node.val >= max_val:
                traverse_count += 1
            max_val = max(max_val, node.val)
            if node.left: traverse(node.left, max_val)
            if node.right: traverse(node.right, max_val)
        if root:
            traverse(root, float('-inf'))
        return traverse_count

# 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 goodNodes(self, root: TreeNode) -> int:
        return(self.helper(root))
    
    
    def helper(self,root,maxVal = -9999):
        total = 0
        if root.val >= maxVal:
            total += 1
            maxVal = root.val
        if root.left:
            total += self.helper(root.left,maxVal)
        if root.right:
            total += self.helper(root.right,maxVal)
        
        return total

# 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 goodNodes(self, root: TreeNode) -> int:
        def dfs(node, q):
            if node:
                res=0
                print (node.val,\" hello \",q)
                if node.val>= q:
                    res+=1
                res+=dfs(node.left,max(node.val,q))
                res+=dfs(node.right,max(node.val,q))
                return res
            else: return 0

        
        return dfs(root,-10001)
        

# 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 goodNodes(self, root: TreeNode) -> int:
        
        count = 0
        stack = [(root, root.val)]
        
        while len(stack) > 0:
            popped = stack.pop()
            node = popped[0]
            curMax = popped[1]
            if node.val >= curMax:
                count += 1
            if node.right is not None:
                stack.append((node.right, max(node.right.val, curMax)))
            if node.left is not None:
                stack.append((node.left, max(node.left.val, curMax)))
        return count


# 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 goodNodes(self, root: TreeNode) -> int:
        return self.countGoodNodes(root, -999999)

    def countGoodNodes(self, node, maxSoFar):
        if node is None:
            return 0

        newMax = max(maxSoFar, node.val)
        return int(node.val >= maxSoFar) + self.countGoodNodes(node.left, newMax) + self.countGoodNodes(node.right, newMax)

# 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 goodNodes(self, root: TreeNode) -> int:
        ans = 0
        q = [(root, float('-inf'))]
        
        while q:
            (curr, maxvals) = q.pop(0)
            if curr.val >= maxvals:
                ans += 1
                maxvals = curr.val
                
            if curr.left: q.append((curr.left,maxvals))
            if curr.right: q.append((curr.right,maxvals))
        
        return ans


# 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 goodNodes(self, root: TreeNode) -> int:
        stack = []
        ans = [0]
        
        def dfs(root):
            if not stack or root.val >= stack[-1].val:
                stack.append(root)
                ans[0] += 1
            if root.left:
                dfs(root.left)
            if root.right:
                dfs(root.right)
            if stack and root == stack[-1]:
                stack.pop()
        
        dfs(root)
        return ans[0]

# 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 helper(self,root,output,count):
        if(root is None):
            return 
        flag=False
        for ele in output:
            if(ele>root.val):
                flag=True
        if(flag==False):
            count[0]+=1
        output.append(root.val)
        self.helper(root.left,output,count)
        self.helper(root.right,output,count)
        output.pop()
    def goodNodes(self, root: TreeNode) -> int:
        count=[0]
        output=[]
        self.helper(root,output,count)
        return count[0]


# 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 goodNodes(self, root: TreeNode) -> int:
        traverse_count = 0
        def traverse(node, max_val=float('-inf')):
            nonlocal traverse_count
            if not node:
                return
            if node.val >= max_val:
                traverse_count += 1
            max_val = max(max_val, node.val)
            traverse(node.left, max_val)
            traverse(node.right, max_val)
        traverse(root)
        return traverse_count

# 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 goodNodes(self, root: TreeNode) -> int:
        
        maximum = root.val
        self.count = 0
        def dfs(node,maximum):
            if not node:return
            if node.val >= maximum:
                self.count += 1
                maximum = max(maximum,node.val)
            dfs(node.left,maximum)
            dfs(node.right,maximum)
            
        dfs(root,maximum)
        return self.count

# 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 goodNodes(self, root: TreeNode) -> int:
        
    
        
        def dfs(root,path):
            
            if root:
                indx=bisect.bisect(path,root.val)
                if indx==len(path):
                    # res.append(root.val)
                    self.count+=1
                dfs(root.left,path[:indx]+[root.val]+path[indx:])
                dfs(root.right,path[:indx]+[root.val]+path[indx:])
        # res=[]
        self.count=0
        dfs(root,[])
        # print(res)
        return self.count
                
                


# 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 goodNodes(self, root: TreeNode) -> int:
        res=[]
        cnt=0
        def dfs(node):
            nonlocal cnt
            res.append(node.val)
            
            if res[-1] == max(res):
                cnt+=1
                
            if node.left:
                dfs(node.left)
                
            if node.right:
                dfs(node.right)
                
            if res:
                res.pop()
                
        dfs(root)
        return cnt

# 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 goodNodes(self, root: TreeNode) -> int:
        def dfs(r, val = float('-inf')):
            if r:
                ans = 1 if r.val >= val else 0
                new_val = max(r.val, val)
                ans += dfs(r.left, new_val)
                ans += dfs(r.right, new_val)
                return ans
            return 0
        return dfs(root)

# 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 goodNodes(self, root: TreeNode) -> int:
        count = 0
        return 1 + self.helper(root.left, root.val) + self.helper(root.right, root.val)
    
    def helper(self, root: TreeNode, m: int) -> int:
        if root:
            if root.val >= m:
                return 1 + self.helper(root.left, max(root.val,m)) + self.helper(root.right, max(root.val,m))
            else:
                return self.helper(root.left, max(root.val,m)) + self.helper(root.right, max(root.val,m))
            
        else:
            return 0

# 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 goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        res = 1
        parents, children = [(root, root.val)], []
        while parents:
            for node, val in parents:
                if node.left:
                    if node.left.val >= val:
                        res += 1
                    children.append((node.left, max(val, node.left.val)))
                if node.right:
                    if node.right.val >= val:
                        res += 1
                    children.append((node.right, max(val, node.right.val)))
            parents = children
            children = []
            
        return res

# 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:
    counter = 0
    
    def goodNodes(self, root: TreeNode) -> int:
        self.counter = 0
        self._goodNodes(root, root.val)
        return self.counter
        
    def _goodNodes(self, root: TreeNode, current_max: int):
        if not root:
            return
        
        if root.val >= current_max:
            self.counter += 1
        
        self._goodNodes(root.left, max(current_max, root.val))
        self._goodNodes(root.right, max(current_max, root.val))

# 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 goodNodes(self, root: TreeNode) -> int:
        def dfs(root, mval):
            if not root:
                return 0
            l = dfs(root.left, root.val if root.val > mval else mval)
            r = dfs(root.right, root.val if root.val > mval else mval)
            return l + r + (1 if root.val >= mval else 0)
        return dfs(root, float(\"-inf\"))

# 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:
    '''
    - as we traverse down, we measure the maxSoFar and compare current 
    node with that
    - current node is good if >= maxSoFar, so count as one
    - can traverse recursively
    '''
    def goodNodes(self, root: TreeNode) -> int:
        def traverse(node, maxSoFar=float(\"-inf\")):
            # check base case (null node)
            if not node:
                return 0
            
            # process node
            count = 1 if node.val >= maxSoFar else 0
            maxSoFar = max(maxSoFar, node.val)
            
            # traverse children, adding count along the way
            return traverse(node.left, maxSoFar) + traverse(node.right, maxSoFar) + count
            
        if not root:
            return 0
        return traverse(root)
        
        

# 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 __init__(self):
        self.total_count = 0
        
    def goodNodes(self, root: TreeNode) -> int:
        return self.goodNodesHelper(root, float('-inf'))
        
    def goodNodesHelper(self, root, max_so_far):
        if not root:
            return 
        if max_so_far <= root.val:
            max_so_far = root.val
            self.total_count += 1
        self.goodNodesHelper(root.left, max_so_far)
        self.goodNodesHelper(root.right, max_so_far)
        return self.total_count