Count Number of Good Nodes

Question

problem statement

I am having trouble understanding what is wrong with my code and understanding the constraint below.

My pseudocode:

1. Traverse the tree Level Order and construct the array representation (input is actually given as a single root, but they use array representation to show the full tree)
2. iterate over this array representation, skipping null nodes
3. for each node, let's call it X, iterate upwards until we reach the root checking to see if at any point in the path, parentNode > nodeX, meaning, nodeX is not a good node.
4. increment counter if the node is 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]

First of all: My confusion on the constraint is that, the automated tests are giving input such as [2,4,4,4,null,1,3,null,null,5,null,null,null,null,5,4,4] and if we follow the rules that childs are at c1 = 2k+1 and c2 = 2k+2 and parent = (k-1)//2 then this means that there are nodes with value null

Secondly: For the input above, my code outputs 8, the expected value is 6, but when I draw the tree from the array, I also think the answer should be 8!

tree of input

# 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:
        
        
        arrRepresentation = []
        
        queue = []
        
        queue.append(root)
        
        # while queue not empty
        while queue:
            # remove node
            node = queue.pop(0)
            if node is None:
                arrRepresentation.append(None)
                
            else:
                arrRepresentation.append(node.val)

            
          
            if node is not None:
                # add left to queue
                queue.append(node.left)

                # add right to queue
                queue.append(node.right)
            
        
        print(arrRepresentation)
        goodNodeCounter = 1

                
        # iterate over array representation of binary tree
        for k in range(len(arrRepresentation)-1, 0, -1):
            child = arrRepresentation[k]
            if child is None:
                continue
            isGoodNode = self._isGoodNode(k, arrRepresentation)
            print('is good: ' + str(isGoodNode))

            if isGoodNode:
                goodNodeCounter += 1
                
           
                
            
        
        return goodNodeCounter

        
    def _isGoodNode(self, k, arrRepresentation):
        
        child = arrRepresentation[k]
        print('child: '+str(child))
        # calculate index of parent
        parentIndex = (k-1)//2
        
        isGood = True
        # if we have not reached root node
        while parentIndex >= 0:
            parent = arrRepresentation[parentIndex]
            print('parent: '+ str(parent))
            # calculate index of parent
            parentIndex = (parentIndex-1)//2
            
            if parent is None:
                continue
            
            if parent > child:
                isGood = False
                break
                
           
                
        return isGood
        
        
        

Answer 1

Recursion might be easier:

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def good_nodes(root, maximum=float('-inf')):
    if not root: # null-root
        return 0

    is_this_good = maximum <= root.val # is this root a good node?

    maximum = max(maximum, root.val) # update max
    good_from_left = good_nodes(root.left, maximum) if root.left else 0
    good_from_right = good_nodes(root.right, maximum) if root.right else 0

    return is_this_good + good_from_left + good_from_right

tree = Node(2, Node(4, Node(4)), Node(4, Node(1, Node(5, None, Node(5, Node(4), Node(4)))), Node(3)))
print(good_nodes(tree)) # 6

Basically, recursion traverses the tree while updating the maximum number seen so far. At each iteration, the value of a root is compared with the maximum, incrementing the counter if necessary.

Answer 2

Since you wanted to solve with breadth first search:

from collections import deque

class Solution:
    def goodNodes(self,root:TreeNode)->int:
        if not root:
            return 0        
        queue=deque()
        # run bfs  with track of max_val till its parent node
        queue.append((root,-inf))
        res=0
        while queue:
            current,max_val=queue.popleft()
            if current.val>=max_val:
                res+=1
            if current.left:   
                queue.append((current.left,max(max_val,current.val)))
            
            if current.right:
                queue.append((current.right,max(max_val,current.val)))           
        return res

I added the node and its max_value till its parent node. I could not add a global max_value, because look at this tree:

For the first 3 nodes, you would have this [3,1,4] and if you were keeping the max_val globally, max_val would be 4.

Now next node would be 3, leaf node on the left. Since max_node is 4, 3<4 would be incorrect so 3 would not be considered as good node. So instead, I keep track of max_val of each node till its parent node

Answer 3

The binary heap you provided corresponds to the folloring hierarchy:

tree = [2,4,4,4,None,1,3,None,None,5,None,None,None,None,5,4,4]
printHeapTree(tree)

    2
   / \
  4   4
 /   / \
4   1   3
         \
          5

In that tree, only item value 1 has an ancestor that is greater than itself. The 6 other nodes are good, because they have no ancestor that are greater than themselves (counting the root as good).

Note that there are values in the list that are unreachable because their parent is null (None) so they are not part of the tree (this could be a copy/paste mistake though). If we replace these None values by something else to make them part of the tree, we can see where the unreachable nodes are located in the hierarchy:

t = [2,4,4,4,'*', 1,3,'*',None, 5,None, None,None,None,5,4,4]
printHeapTree(t)

          2
       __/ \_
      4      4
     / \    / \
    4   *  1   3
   /   /        \
  *   5          5
 / \
4   4

This is likely where the difference between a result of 8 (not counting root as good) vs 6 (counting root as good) comes from.

You can find the printHeapTree() function here.