$($e$)(20$ points$)$ Consider the following node implementation for a

red$-$black tree:

Write a

that takes a pointer to the root of a red$-$black tree and an integer

parameter named blackCount, and determines if every path

from node root to an external node has the given number of

black nodes. It returns true if the number of black nodes on all

paths from the root to external nodes is equal to the given

parameter, blackCount; false otherwise.

Use the following prototype:

bool isBlackHeight$($ RBNode$*$ root, int blackCount $)$;

Important: Your solution MUST be recursive and MUST have

run$-$time complexity of $O(n)$ and space complexity of $O(1)($not

counting the input tree$)$ where $n$ is the number of items in the

red$-$black tree.