Good morning to you! Hope your day has started on the right note. It is a cloudy Friday in the Twin Cities of Minneapolis and St. Paul. Hopefully the weather will improve during the day.
Earlier this week I was chatting with a software engineer. We were discussing a problem that was split into two parts. What was interesting is that the first part was to be performed by a different engineer and the second by the person solving the problem. I thought the description (completely verbal) was interesting and appealing.
We have a task and will be split by two engineers. The first part was supposed to be done by a different engineer. The second part, in this case, by a different person. The team was given a simple arithmetic operation with integers. The first member would take care of parsing the expression and the second team member would receive a binary tree representing the arithmetic expression. The example described: 5 * (4 - 2) If we evaluate the expression the answer would be: 10 This was the only test case described. A diagram with the associated binary tree is provided: * / \ 5 - / \ 4 2 No binary tree representation is provided.
As I mentioned, there was no written description of the problem. What you see is my recollection based on our conversation.
As you might know, I have tackled several problems with binary tree in this blog. I have written several utilities in order not to reinvent the wheel.
My first approach was to provide the following description for the binary tree:
*, 5, -,null,null,4,2
I have in a library ways to get from a string to a binary tree. In addition, not that is of use in this problem, we can also go from a binary tree to a string.
We figured that it would work, but required additional code.
/**
* Receive the root of a binary
* tree and recursively evaluate it.
* Recursive function.
*/
public static int evaluate(TreeNode root) {
}
As far as I can recall, the signature for the function in question was not provided, so for a first pass a function that accepts the binary tree and returns the integer result made sense.
main <<< preOrder: * 5 - 4 2 main <<< inOrder: 5 * 4 - 2 main <<< postOrder: 5 4 2 - * main <<< evaluate: 10 main <<< eval: 10 main <<< preOrder: + * 5 4 - 100 20 main <<< inOrder: 5 * 4 + 100 - 20 main <<< postOrder: 5 4 * 100 20 - + main <<< evaluate: 100 main <<< eval: 100 main <<< preOrder: + * 5 4 - 100 / 20 2 main <<< inOrder: 5 * 4 + 100 - 20 / 2 main <<< postOrder: 5 4 * 100 20 2 / - + main <<< evaluate: 110 main <<< eval: 110
The three test cases start with the representation of the results of traversing a binary tree (which was never provided) using a pre order, in order and post order traversals.
I did this to better understand the contents of the binary tree and see if a light bulb would come on. Please take a few minutes and compare the arithmetic expression with the different traversals of the associated binary tree. I will wait … OK, you are back so let’s continue.
I have to admit that I have only owned Hewlett Packard calculators. Initially they only worked using Reverse Polish Notation. The post order traversal looks like a good fit for this problem.
It seems that we have two implementations which provide the same result. That is good news.
In the first implementation which I called more of a brute force approach, it took a lot of test and trial to get to the code that we will see shortly. For the second implementation, I moved quickly and in less than half hour it moved from concept to implementation.
Since I started working with previous code, I used a modified TreeNode class. The fields of interest are `val`, `left` and `right`. I should have declared the TreeNode class in the same file, but as I said I started with a completely different approach.
We will solve this problem using the Java programming language and the VSCode IDE on a Windows computer. We will first need to implement a test scaffold to provide a binary tree implementation representing the data that would be provided by the other team member.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** test case 1 ****
TreeNode root = new TreeNode("*");
root.left = new TreeNode("5");
root.right = new TreeNode("-");
root.right.left = new TreeNode("4");
root.right.right = new TreeNode("2");
// **** test case 2 ****
// TreeNode root = new TreeNode("+");
// root.left = new TreeNode("*");
// root.left.left = new TreeNode("5");
// root.left.right = new TreeNode("4");
// root.right = new TreeNode("-");
// root.right.left = new TreeNode("100");
// root.right.right = new TreeNode("20");
// **** test case 3 ****
// TreeNode root = new TreeNode("+");
// root.left = new TreeNode("*");
// root.left.left = new TreeNode("5");
// root.left.right = new TreeNode("4");
// root.right = new TreeNode("-");
// root.right.left = new TreeNode("100");
// root.right.right = new TreeNode("/");
// root.right.right.left = new TreeNode("20");
// root.right.right.right = new TreeNode("2");
// ???? ????
System.out.println("main <<< preOrder: ");
preOrder(root);
System.out.println();
// ???? ????
System.out.println("main <<< inOrder: ");
inOrder(root);
System.out.println();
// ???? ????
System.out.println("main <<< postOrder: ");
postOrder(root);
System.out.println();
// **** evaluate binary tree and display result ****
System.out.println("main <<< evaluate: " + evaluate(root));
// **** evaluate binary tree and display result ****
System.out.println("main <<< eval: " + eval(root));
}
Let’s concentrate on the first test case. I have three test cases. The nice thing is that you can come up with an arithmetic expression; evaluate it, manually make an associated binary tree, and then run the code. The results should match!
We start by manually generating the binary tree for the only expression that we were provided. I believe it is easy to follow what is going on.
We then call a set of functions to display the results of different tree traversals.
Finally we call the two implementations and display the returned results.
/**
* Binary tree pre order traversal.
* Recursive function.
*/
public static void preOrder(TreeNode node) {
if (node != null) {
// **** display node value ****
System.out.print(node.val + " ");
// **** visit left child ****
preOrder(node.left);
// **** visit right child ****
preOrder(node.right);
}
}
This is a text book approach to perform a binary tree pre order traversal. You have seen the use of this function / method several times in this blog.
/**
* Binary tree post order traversal.
* Recursive function.
*/
public static void postOrder(TreeNode node) {
if (node != null) {
// **** visit left child ****
postOrder(node.left);
// **** visit right child ****
postOrder(node.right);
// **** display node value ****
System.out.print(node.val + " ");
}
}
This is also a text book approach to perform a binary tree post order traversal. You have seen the use of this function / method several times in this blog.
/**
* Binary tree in order traversal.
* Recursive function.
*/
public static void inOrder(TreeNode node) {
if (node != null) {
// **** visit left child ****
inOrder(node.left);
// **** display node value ****
System.out.print(node.val + " ");
// **** visit right child ****
inOrder(node.right);
}
}
Finally the text book approach to perform a binary in order traversal. You have also seen the use of this function / method several times in this blog.
/**
* Receive the root of a binary
* tree and recursively evaluate it.
* Recursive function.
*/
public static int evaluate(TreeNode root) {
// **** base case ****
if (root == null || root.val.equals("null")) return 0;
// **** leaf node i.e, an integer ****
if (root.left == null && root.right == null)
return Integer.parseInt(root.val);
// **** evaluate left subtree ****
int leftEval = evaluate(root.left);
// **** evaluate right subtree ****
int rightEval = evaluate(root.right);
// **** determine which operator to apply ****
if (root.val.equals("+"))
return leftEval + rightEval;
if (root.val.equals("-"))
return leftEval - rightEval;
if (root.val.equals("*"))
return leftEval * rightEval;
return leftEval / rightEval;
}
This is the first implementation with multiple modifications. Since it is recursive we have a base condition.
If the leaf node meets some criteria we conclude we have a node with an integer, not an operand.
We evaluate the left sub tree followed by the right sub tree.
Finally we look at the operation we need to perform. Looks like a post order traversal with some checks. Seems to work but I believe we could get some code that might be easier to understand and follow.
// **** used by eval function ****
static Stack<Integer> stack = null;
We will use s global stack. We will use it to store the integer operands.
/**
* Entry point for this implementation.
*/
public static int eval(TreeNode node) {
// **** initialization ****
stack = new Stack<Integer>();
// **** evaluate binary tree ****
evalStack(node);
// **** return result ****
return stack.pop();
}
We start by creating a fresh stack.
We then call a recursive function to evaluate the binary tree. As the function visits the different nodes, the stack is updated. The last and only remaining entry will represent the result.
When all is done, this function returns the result which is extracted from the stack.
/**
* Recursive call.
*/
private static void evalStack(TreeNode node) {
if (node != null) {
// **** visit left child ****
evalStack(node.left);
// **** visit right child ****
evalStack(node.right);
// **** process stack ****
if (node.val.compareTo("+") == 0 ||
node.val.compareTo("-") == 0 ||
node.val.compareTo("*") == 0 ||
node.val.compareTo("/") == 0) {
// **** ****
int result = 0;
// **** pop operands ****
int a = stack.pop();
int b = stack.pop();
// **** perform operation ****
if (node.val.compareTo("+") == 0)
result = b + a;
else if (node.val.compareTo("-") == 0)
result = b - a;
else if (node.val.compareTo("*") == 0)
result = b * a;
else
result = b / a;
// **** push result ****
stack.push(result);
} else
stack.push(Integer.parseInt(node.val));
}
}
This function is closely modeled to a post order tree traversal.
We visit the left followed by the right sub trees.
When we visit the current node we decide if we have an operation to perform or if it is not an operation, we just push into the stack the operand for a future operation.
If we encounter an operation, we pop from the stack two operands. Based on the current operand we perform the operation on hand. The result is then pushed into the top of the stack.
I fully understand that we have not dealt with additional operands, functions, or single arguments. We do not work for Hewlett Packard ;o)
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode). Not sure if this problem comes from a site or was created by the engineer I was speaking with.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John