Yesterday evening I was browsing different sites on my phone.
Found on Medium the article LeetCode 1448: Count Good Nodes in Binary Tree by Pierre-Marie Poitevin. If you follow my blog, you probably noticed that in the past couple weeks I have been looking at recursive problems on the LeetCode web site. So earlier today I decided to give it a try.
Originally I was going to write about load balancers today, but I am in the process of reading the paper: Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web by David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. As soon as I have time to finish reading it, I will generate a post on load balancers.
The forecast for the day called for rain. So far it has been dry and the 
temperature in the mid 50’s. My wife and I have been using the grill to cook lunch for several months. It seems that we need to move back to the range and oven. It is quite nice for me because she calls me when lunch is served; otherwise we take about 30 additional minutes a day to cook in the grill.
The main subject for this post is LeetCode 1448 Count Good Nodes in Binary Tree problem. If you are interested please take a look at the problem, think about how to solve it, solve it if you have time, and then continue reading here. It is a good idea to always attempt to solve a problem before looking at the solution.
As usual, I will develop the code in my computer using my preferred tools which are the ones I use for work. This implies that in addition to solving the problem at hand, I will spend time writing and copying code for the test scaffolding. Note that the test scaffolding is not part of the solution for the problem. That said I will use Java as a programming language, the VSCode IDE and Windows 10 as my computer. The main reason for Windows is that I use it to write and store the documents for WordPress.
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. 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].
I guess that is you are still reading, you are interested in this problem. The idea is to count in a binary tree (BT) the number of “good nodes”. The LeetCode description defines what a “good node” is. It also provides some constraints. To be honest with you, I did not pay attention to them.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int goodNodes(TreeNode root) {
}
}
LeetCode provides the definition for the TreeNode class which seems to be used for most (never generalize) BT problems. The skeleton for the function we need to fill in to solve the problem is also included.
3,1,4,3,null,1,5 main <<< root: 3 1 3 1 4 5 main <<< output: 4 main <<< output: 4 3,3,null,4,2 main <<< root: 4 3 2 3 main <<< output: 3 main <<< output: 3 1 main <<< root: 1 main <<< output: 1 main <<< output: 1 -1,5,-2,4,4,2,-2,null,null,-4,null,-2,3,null,-2,0,null,-1,null,-3,null,-4,-3,3,null,null,null,null,null,null,null,3,-3 main <<< root: 4 5 3 0 -4 4 -1 -1 -2 2 -3 3 -2 -2 -4 -2 3 -3 -3 main <<< output: 5 main <<< output: 5
The screen dump of the output of the test scaffolding shows four tests. The input line is a representation in level order for the contents of the BT. The next line displays the BT using an in-order traversal. I use it to verify that all 
is well so far and we were able to load in the BT. Two lines follow with the result for the specified BT. As usual will take a look at both. When I am working on exercises, time permitting, I like to experiment during and after I have an accepted solution. In this case both solutions are similar and were accepted by LeetCode.
Based on the requirements, this problem could be solved using a Depth First Search approach. DFS is a tree traversal algorithm.
/**
* Definition for a binary tree node.
*/
class TreeNode {
// **** class members ****
int val;
TreeNode left;
TreeNode right;
// **** constructors ****
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
As we saw earlier in this post, LeetCode provides the definition of the TreeNode class as a reference. Since we are developing the test scaffolding, we need to make use of the specified class in our solution. The class is an edited (nothing added) copy of what LeetCode provided.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read and split line describing the BT ****
String[] arr = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// **** binary tree root ****
TreeNode root = null;
// **** populate the BT ****
root = populateTree(arr);
// ???? ????
System.out.print("main <<< root: ");
inOrder(root);
System.out.println();
// **** generate and display the result ****
System.out.println("main <<< output: " + goodNodes(root));
// **** generate and display the result ****
System.out.println("main <<< output: " + goodNodes2(root));
}
We have a pretty straight forward approach. We open a scanner, read and split the BT description in level order, close the scanner, and populate the BT. Then we display it to make sure all is well so far. Finally we call two different functions that should return the same results. They both do.
/**
* This function populates a BT in level order as
* specified by the array.
* This function supports 'null' values.
*/
static TreeNode populateTree(String[] arr) {
// **** root for the BT ****
TreeNode root = null;
// **** auxiliary queue ****
Queue<TreeNode> q = new LinkedList<TreeNode>();
// **** traverse the array of values inserting nodes
// one at a time into the BST ****
for (String strVal : arr)
root = insertValue(root, strVal, q);
// **** clear the queue (the garbage collector will do this) ****
q = null;
// **** return the root of the BST ****
return root;
}
This is the function we will use to load the contents of the BTs. We need some additional code to make this work.
/**
* Enumerate which child in the node at the head of the queue
* (see populateTree function) should be updated.
*/
enum Child {
LEFT,
RIGHT
}
// **** child turn to insert on node at head of queue ****
static Child insertChild = Child.LEFT;
/**
* This function inserts the next value into the specified BST.
* This function is called repeatedly from the populateTree method.
* This function supports 'null' value.
*/
static TreeNode insertValue(TreeNode root, String strVal, Queue<TreeNode> q) {
// **** node to add to the BST in this pass ****
TreeNode node = null;
// **** create a node (if needed) ****
if (!strVal.equals("null"))
node = new TreeNode(Integer.parseInt(strVal));
// **** check is the BST is empty (this becomes the root node) ****
if (root == null)
root = node;
// **** add node to left child (if possible) ****
else if (insertChild == Child.LEFT) {
// **** add this node as the left child ****
if (node != null)
q.peek().left = node;
// **** for next pass ****
insertChild = Child.RIGHT;
}
// **** add node to right child (if possible) ****
else if (insertChild == Child.RIGHT) {
// **** add this node as a right child ****
if (node != null)
q.peek().right = node;
// **** remove node from queue ****
q.remove();
// **** for next pass ****
insertChild = Child.LEFT;
}
// **** add this node to the queue (if NOT null) ****
if (node != null)
q.add(node);
// **** return the root of the BST ****
return root;
}
We define an enum to keep track if we are filling the left or the right child of a node. That is followed by a variable we will use with the enum. The core function decides if and where the new node will be inserted into the BT.
/**
* Traverse the specified BST displaying the values in order.
* This method is used to verify that the BST was properly populated.
*/
static void inOrder(TreeNode root) {
// **** end condition ****
if (root == null)
return;
// **** visit the left sub tree ****
inOrder(root.left);
// **** display the value of this node ****
System.out.print(root.val + " ");
// **** visit the right sub tree ****
inOrder(root.right);
}
This function is used to perform in-order traversal of the nodes in the BT. Note that when we use a BST the values are in ascending order. Since we are not using a BST but a general BT, the display is not as simple to follow. Perhaps we should have performed a breadth order traversal. If interested, you can find such code in several posts that deal with BTs (e.g., Minimum Distance Between BST Nodes).
/**
* 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.
*/
static int goodNodes(TreeNode root) {
// **** check for null BT ****
if (root == null)
return 0;
// **** return count ****
return 1 + // count BT root
goodNodesRec(root.left, root.val) + // count left tree
goodNodesRec(root.right, root.val); // count right tree
}
This is part one of two of a solution. The algorithm uses a DFS approach.
We check if the BT is null and return the obvious result of zero (0). If we have a valid root, then we proceed to call a recursive function based on DFS to return the counts of “good nodes” in the BT.
/**
* 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.
* This is a recursive call.
*/
static int goodNodesRec(TreeNode root, int maxVal) {
// **** base condition ****
if (root == null)
return 0;
// **** initialize count ****
int count = 0;
// **** update count & max value (if needed) ****
if (root.val >= maxVal) {
count++;
maxVal = root.val;
}
// **** traverse left tree ****
count += goodNodesRec(root.left, maxVal);
// **** traverse right tree ****
count += goodNodesRec(root.right, maxVal);
// **** return count ****
return count;
}
This code implements the recursive function which is the second part for the solution. You can see the base case and recursive parts. After taking care of increasing the count for the root value, we recursively call the function to traverse the left and right children. The count of “good nodes” is incremented as needed. When done we return the result.
/**
* Recursive call.
*/
static int dfs(TreeNode root, int max) {
// **** base case ****
if (root == null)
return 0;
// **** initialize count ****
int count = 0;
// **** update count & max value (if needed) ****
if (root.val >= max) {
count++;
max = root.val;
}
// **** recurse ****
count += dfs(root.left, max);
count += dfs(root.right, max);
// **** return count ****
return count;
}
This and the next functions implement a very similar approach. I think that the flavor of the DFS algorithm is better represented here. Keep in mind that there is a large number of problems that can be solved with the DFS approach.
/**
* Call dfs to get the result.
*/
static int goodNodes2(TreeNode root) {
return dfs(root, Integer.MIN_VALUE);
}
This is the entry point for the algorithm. Just copy the one line body into LeetCode followed by the complete definition of the previous function. This approach was also accepted by LeetCode.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1797 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa