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].

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

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:
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


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]


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.count = 0
		self.helper_rec(root, root.val)
		return self.count


class Solution:

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


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


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]


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


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


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


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))


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)


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


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(root.val)
		if root.val >= maxSoFar:
			sumNode.append(root.val)
		maxSoFarNow = max(maxSoFar, root.val)
		self.goodNode(root.left, maxSoFarNow, sumNode)
		self.goodNode(root.right, maxSoFarNow, sumNode)


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


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


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


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


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


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


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


class Solution:

	def goodNodes(self, root: TreeNode) -> int:
		if root is None:
			return 0
		out = [0]

		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]


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))


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


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)


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


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)


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


class Solution:

	def goodNodes(self, root: TreeNode) -> int:
		queue = deque()
		TraverseItem = namedtuple('TraverseItem', ['threshold', 'node'])
		queue.append(TraverseItem(threshold=-100000.0, 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


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


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)


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)


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]


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


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)


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)


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'))


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


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


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)


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


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]


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]


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


class Solution:

	def goodNodes(self, root: TreeNode) -> int:

		def dfs(root, path):
			if root:
				indx = bisect.bisect(path, root.val)
				if indx == len(path):
					self.count += 1
				dfs(root.left, path[:indx] + [root.val] + path[indx:])
				dfs(root.right, path[:indx] + [root.val] + path[indx:])
		self.count = 0
		dfs(root, [])
		return self.count


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)


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


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


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))


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