Hope your weekend is going well. I will start with an unrelated event to the main subject of this post.
When I was working at my first job in Minneapolis, Minnesota the Red Cross would stop by at work for blood drives. They made it simple, so I started to give blood once a year.
Time went by and I decided to do it twice a year (one for my wife and one for me). I had my first appointment for 2023 last Friday afternoon. All went well as usual up to the point in which after the gauze was taped to my arm to protect the area from which the needle was removed. The technician offered a bandage to put pressure over the gauze to protect it for a couple hours. I have always declined and this time was no different.
I thanked the technician, put on my jacket, and headed to the reception area to look for my wife. On my way I picked up a bottle of water.
As I was standing waiting for my wife getting ready to leave, she looked at me with a frightened face. Blood was dripping out the right sleeve of my jacket. It was dripping on the carpet floor. A technician was called and we walked back to check what was going on.
I removed my jacket. My right arm was covered in blood and it continued to drip. The gauze was immediately replaced and I put pressure on it. The technicians cleaned my arm with a cold disinfectant solution. A pressure bandage was applied.
The organizers of the drive were cleaning all blood drops on the carpet and floor. They responded fast and did a good job.
After several apologies we left and drove home. Not sure why this happened, but from now on, I will accept the pressure bandage and will wait for a few minutes before leaving. Imagine if the issue would have occurred while driving or at home. If you donate blood, make sure all is well before leaving the donation site. I will continue my routine donating twice a year!
Now let’s get to the main subject for this post.
About a month ago OpenAI made public the use of ChatGPT for testing. I suggest reading the ChatGPT and GPT-3 articles to get an initial description of the technology. At that point you should be ready to experience the technology by visiting the OpenAi site and experimenting with it.
Since the technology is exposed as a chatbot you simply post a question and it is answered as best as possible. After reading a few articles and documents and watching several YouTube videos it seems that the best approach is to ask a simple base question on the topic of interest, and based on the responses guide ChatGPT to refine the answer until you are satisfied.
I will now describe what my goal is and the questions I asked until what I wanted was provided. It seems that a handful of questions is all that is required to get an answer that is useful. Then you can continue to refine the answers to meet very specific needs.
If you look in my blog, there are many posts that solve problems on binary trees. To populate a binary tree it is efficient to provide a string with the values of the node in Breadth-first search (https://en.wikipedia.org/wiki/Breadth-first_search) order. For example, given the string “1, 2, 3” the representation is of a binary tree with root “1”, left node with value “2” and right node with value “3”. If instead we are provided with the string “1, null, 3” then the root node is still “1”, there is no left node, and the right node for the root is “3”.
Sometime ago I wrote a class with a few methods to help me populate and experiment with different binary trees. We will use the description of LeetCode 111 Minimum Depth of Binary Tree as an example of a problem that requires us to have access to a binary tree.
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Constraints: o The number of nodes in the tree is in the range [0, 10^5]. o -1000 <= Node.val <= 1000 Related Topics: o Tree * Depth-First Search * Breadth-First Search o Binary Tree
To be complete we need to have the definition for a node in our tree.
/**
* 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 minDepth(TreeNode root) {
}
}
The basic binary tree has three elements, the root value, a pointer to the left child and a pointer to the right child. One can then have several constructors that can help on how different algorithms are implemented.
We will not cover the solution of the problem in this post. We are only interested in how to populate the binary tree which is not part of the problem. If interested in this problem, I invite you to read the post LeetCode 111. Minimum Depth of Binary Tree in my blog.
3,9,20,17,5,15,7 main <<< strArr: [3, 9, 20, 17, 5, 15, 7] main <<< arr: [3, 9, 20, 17, 5, 15, 7] populate <<< treeNodeQ: [(val: 3 l: null r: null)] populate <<< integerQ: [9, 20, 17, 5, 15, 7] main <<< inOrder: 17 9 5 3 15 20 7 main <<< postOrder: 17 5 9 15 7 20 3 levelOrder <<< lst: [[3], [9, 20], [17, 5, 15, 7], [null, null, null, null, null, null, null, null]] main <<< levelOrder: 3 9,20 17,5,15,7 null,null,null,null,null,null,null,null main <<< maxDepth: 3 main <<< minDepth: 3 3,9,20,null,null,15,7 main <<< strArr: [3, 9, 20, null, null, 15, 7] main <<< arr: [3, 9, 20, null, null, 15, 7] populate <<< treeNodeQ: [(val: 3 l: null r: null)] populate <<< integerQ: [9, 20, null, null, 15, 7] main <<< inOrder: 9 3 15 20 7 main <<< postOrder: 9 15 7 20 3 levelOrder <<< lst: [[3], [9, 20], [null, null, 15, 7], [null, null, null, null]] main <<< levelOrder: 3 9,20 null,null,15,7 null,null,null,null main <<< maxDepth: 3 main <<< minDepth: 2 3,9,20,null,15,7,null main <<< strArr: [3, 9, 20, null, 15, 7, null] main <<< arr: [3, 9, 20, null, 15, 7, null] populate <<< treeNodeQ: [(val: 3 l: null r: null)] populate <<< integerQ: [9, 20, null, 15, 7, null] main <<< inOrder: 9 15 3 7 20 main <<< postOrder: 15 9 7 20 3 levelOrder <<< lst: [[3], [9, 20], [null, 15, 7, null], [null, null, null, null]] main <<< levelOrder: 3 9,20 null,15,7,null null,null,null,null main <<< maxDepth: 3 main <<< minDepth: 3 3,9,20,15,null,null,7 main <<< strArr: [3, 9, 20, 15, null, null, 7] main <<< arr: [3, 9, 20, 15, null, null, 7] populate <<< treeNodeQ: [(val: 3 l: null r: null)] populate <<< integerQ: [9, 20, 15, null, null, 7] main <<< inOrder: 15 9 3 20 7 main <<< postOrder: 15 9 7 20 3 levelOrder <<< lst: [[3], [9, 20], [15, null, null, 7], [null, null, null, null]] main <<< levelOrder: 3 9,20 15,null,null,7 null,null,null,null main <<< maxDepth: 3 main <<< minDepth: 3 2,null,3,null,4,null,5,null,6 main <<< strArr: [2, null, 3, null, 4, null, 5, null, 6] main <<< arr: [2, null, 3, null, 4, null, 5, null, 6] populate <<< treeNodeQ: [(val: 2 l: null r: null)] populate <<< integerQ: [null, 3, null, 4, null, 5, null, 6] main <<< inOrder: 2 3 4 5 6 main <<< postOrder: 6 5 4 3 2 levelOrder <<< lst: [[2], [null, 3], [null, 4], [null, 5], [null, 6], [null, null]] main <<< levelOrder: 2 null,3 null,4 null,5 null,6 null,null main <<< maxDepth: 5 main <<< minDepth: 5 0 main <<< strArr: [0] main <<< arr: [0] populate <<< treeNodeQ: [(val: 0 l: null r: null)] populate <<< integerQ: [] main <<< inOrder: 0 main <<< postOrder: 0 levelOrder <<< lst: [[0], [null, null]] main <<< levelOrder: 0 null,null main <<< maxDepth: 1 main <<< minDepth: 1 null main <<< strArr: [null] main <<< arr: [null] main <<< inOrder: main <<< postOrder: levelOrder <<< lst: [] main <<< levelOrder: main <<< maxDepth: 0 main <<< minDepth: 0
This last screen capture contains a set of examples of different binary trees. Each test case starts with a string of integers e.g., “3,9,20,17,5,15,7” which is used by a utility to create and populate a binary tree. Once populated we display the binary tree in different ways i.e., inOrder, postOrder, and level order. The last two lines of each test case display the max depth and the min depth of the associated binary tree.
If we take a look at the second example, which uses the string “3,9,20,null,null,15,7”, it refers to a different binary tree. The first two levels are the same. In the third level, node “9” does not have children and node “20” has a left node with value “15” and a right node with a value “7”.
When I solve a problem I like to provide a test scaffold. That allows me to experiment with different values. A modifies test scaffold for the problem of interest follows:
/**
* Test scaffold.
* !!!! NOT PART OF SOLUTION !!!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and populate string[] for binary tree ****
String[] strArr = br.readLine().trim().split(",");
// ***** close the buffered reader ****
br.close();
// ????? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** generate Integer[] to create and populate binary tree ****
int len = strArr.length;
Integer[] arr = new Integer[len];
for (int i = 0; i < len; i++)
arr[i] = strArr[i].equals("null") ? null : Integer.parseInt(strArr[i]);
// ????? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create binary tree ****
BST bt = new BST();
// **** convert int[] arr to list ****
List<Integer> levelOrderValues = Arrays.stream(arr)
//.boxed()
.collect(Collectors.toList());
// ???? ????
System.out.println("main <<< levelOrderValues: " + levelOrderValues);
// // **** populate per level the binary tree [0] ****
// bt.root = bt.populate(levelOrderValues);
// // **** populate per level the binary tree using ChatGPT suggestion
// // first attempt (fails when it encounters null input values) [1] ****
// bt.root = bt.populateGPT(levelOrderValues);
// **** populate per level the binary tree using ChatGPT suggestion
// second attempt (seems to work great) [2] ****
bt.root = bt.populateTreeGPT(levelOrderValues);
// ???? in-order traversal ????
System.out.println("main <<< inOrder: " + bt.inOrder());
// ???? post-order traversal ????
System.out.println("main <<< postOrder: " + bt.postOrder());
// ???? level-order traversal ????
System.out.println("main <<< levelOrder: " + bt.levelOrder());
// ???? ????
System.out.println("main <<< maxDepth: " + bt.maxDepth(bt.root));
// **** call the function of interest and display result ****
System.out.println("main <<< minDepth: " + minDepth(bt.root));
}
Towards the middle of the code we have a levelOrderValues list of integers. The code is followed by three different methods that attempt to populate the current binary tree.
The first method is named populate() and is the first incarnation of the method I developed to populate a binary tree. I generated the first implementation a few years ago, and have made changes with time. As you can tell by looking at the code that follows, the class BST has also grown with time with different methods used to traverse binary and binary search trees.
Please note that the sample output we have in this post matches the source code for the test scaffold. We just display the output of the last method populateTreeGTP().
/**
* Populate binary tree per level.
* My original code which did not use GPT to generate.
*/
public TreeNode populate(List<Integer> levelOrderValues) {
// **** sanity checks ****
if (levelOrderValues == null || levelOrderValues.size() == 0) return null;
if (levelOrderValues.get(0) == null) return null;
// **** initialization ****
Queue<TreeNode> treeNodeQ = new LinkedList<>();
Queue<Integer> integerQ = new LinkedList<>();
// **** prime the tree node queue ****
TreeNode node = new TreeNode(levelOrderValues.get(0));
treeNodeQ.offer(node);
// **** populate integer queue ****
for (int i = 1; i < levelOrderValues.size(); i++)
integerQ.offer(levelOrderValues.get(i));
// **** loop while the queue is not empty ****
while (!integerQ.isEmpty()) {
// **** ****
Integer leftVal = integerQ.poll();
Integer rightVal = integerQ.poll();
TreeNode current = treeNodeQ.poll();
// **** insert left node ****
if (leftVal != null) {
TreeNode left = new TreeNode(leftVal);
current.left = left;
treeNodeQ.offer(left);
}
// **** insert right node ****
if (rightVal != null) {
TreeNode right = new TreeNode(rightVal);
current.right = right;
treeNodeQ.offer(right);
}
}
// **** return root of binary tree ****
return node;
}
We start this method by performing some sanity checks followed by an initialization step. After priming the root of the binary tree, we populate a local queue. I should probably remove it, but like I said, this code does not represent a problem, it is just a utility which does not require much optimization. If you follow my blog you might find a more optimized implementation in the future.
The main loop gets data from the integerQ and inserts it into the binary tree. Note that “null” values are skipped.
When all is said and done the root of the binary tree is returned to the caller.
/**
* Populate binary tree per level.
* This code was generated by ChatGPT and edited to match variable names.
* This code does not work when an input node is null!!!!
*/
public TreeNode populateGPT(List<Integer> levelOrderValues) {
// **** sanity check(s) ****
if (levelOrderValues.size() == 0) return null;
// **** initialization ****
TreeNode root = null;
// **** ****
if (levelOrderValues.get(0) != null)
root = new TreeNode(levelOrderValues.get(0));
// **** ****
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) queue.add(root);
// **** ****
int i = 1;
while (!queue.isEmpty() && i < levelOrderValues.size()) {
// **** remove head node ****
TreeNode node = queue.poll();
// ???? ????
System.out.println("populateGPT <<< node: " + node.toString());
// **** ****
if (node.left == null && levelOrderValues.get(i) != null) {
node.left = new TreeNode(levelOrderValues.get(i));
queue.add(node.left);
i++;
}
// **** ****
if (node.right == null && levelOrderValues.get(i) != null) {
node.right = new TreeNode(levelOrderValues.get(i));
queue.add(node.right);
i++;
}
}
// **** return root of binary tree ****
return root;
}
This is the code that I got from ChatGPT on my first attempt at experimenting with it. If you are interested, modify the test scaffold by commenting and uncommenting lines and give it a try. When the code encounters a “null” it stops populating the binary tree. To be honest with you, I felt somewhat disappointed with the technology. As you can see the code attempts to take care of the “null” nodes indicating that I requested such behavior, but the result was not good enough.
This morning I decided to start from scratch and give ChatGPT a second attempt at solving the same problem.
My questions follow:
Q1. How to traverse a binary tree per level? Q2. Using the output of a "level order traversal", how do you populate a binary tree? Q3. What if some input values are null? Q4. Could you convert the code to Java? Q5. Could you change the input to a List<Integer> instead of Integer[]?
The last question motivated the following answer from ChatGPT:
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
public TreeNode populateTree(List<Integer> levelOrder) {
if (levelOrder.size() == 0) {
return null;
}
TreeNode root = new TreeNode(levelOrder.get(0));
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
if (i < levelOrder.size() && levelOrder.get(i) != null) {
current.left = new TreeNode(levelOrder.get(i));
queue.add(current.left);
}
if (i + 1 < levelOrder.size() && levelOrder.get(i + 1) != null) {
current.right = new TreeNode(levelOrder.get(i + 1));
queue.add(current.right);
}
i += 2;
}
return root;
}
I tried all the test cases and they all seem to pass. I then edited the code and came up with:
/**
* This code was generated by GPT with similar questions as I did before.
* The first time it did not work.
* The second time works very well !!!!
* @param levelOrder
* @return
*/
public TreeNode populateTreeGPT(List<Integer> levelOrderValues) {
// **** sanity checks ****
if (levelOrderValues == null || levelOrderValues.size() == 0) return null;
if (levelOrderValues.get(0) == null) return null;
// **** initialization ****
TreeNode root = new TreeNode(levelOrderValues.get(0));
Deque<TreeNode> queue = new LinkedList<>();
// **** prime the queue ****
queue.add(root);
// **** ****
int i = 1;
while (!queue.isEmpty()) {
// **** ****
TreeNode current = queue.poll();
// **** insert left node (if needed) ****
if (i < levelOrderValues.size() && levelOrderValues.get(i) != null) {
current.left = new TreeNode(levelOrderValues.get(i));
queue.add(current.left);
}
// **** insert right noed (if needed) ****
if (i + 1 < levelOrderValues.size() && levelOrderValues.get(i + 1) != null) {
current.right = new TreeNode(levelOrderValues.get(i + 1));
queue.add(current.right);
}
// **** update input index ****
i += 2;
}
// **** return the root of the binary tree ****
return root;
}
What can I tell you, it works and in this case it took exactly a handful of questions. I am very pleased with how ChatGPT works so far. Will generate a couple more tests which will have associated posts.
If interested in the complete code for this post you can find it at my FirstChatGPTPost GitHub repository.
Enjoy,
John