Good day!!! Hope all is going well for you. It is Friday and has been a very stressful week for me. Glad that the weekend is just around the corner.
Today we are going to cover a problem which a software engineer and I discussed earlier this week, but for some reason or the other, we did not generate code at the time. We just talked about it.
We are given a binary tree with integer values and two different nodes in the binary tree, we must return the sum of the values of the nodes that connect p and q inclusive. Constraints: o -1000 <= val <= 1000 o 2 <= n <= 200
As you can see, we are given a binary tree populated with integers. Do not recall if all integers were included. We will assume, since I am writing the requirements as we speak, that the values for the nodes are in the specified range and the number of nodes in the binary tree should not exceed the specified value.
What we need to do is implement an algorithm in which given two nodes from the binary tree, we should return the sum of all nodes in between including the values of the two nodes.
5
/ \
/ \
3 4
/ \ / \
/ \ / \
7 2 1 9
This diagram illustrates a binary tree with 7 nodes. Our first test case will provide us with a similar binary tree and we will be asked to determine the sum of the values between node 7 and node 9 and then between nodes 9 and 7. As we should expect both queries should return the same value. Note that any two pairs of nodes may be selected for a query.
int sumNodes(TreeNode root, TreeNode[] p, TreeNode[] q) {
}
We will be attempting to solve this problem using the Java programming language and the VSCode IDE on a Windows platform. No matter what your choices are for the tools you use, the results should match.
Please note that the function of interest requires 3 arguments. The first is the binary tree and the other two are arrays holding single nodes. We did not discuss specifics about the function of interest. I would assume that it would take 3 arguments, but the last two would just be pointers to the `p` and `q` nodes. For reasons that will become apparent shortly, we will put the nodes into arrays. We could implement two functions. The first with `p` and `q` which would call a second function with similar arguments but the last two would be of type TreeNode[] array with a single node each. We will just skip that step.
We did not have a test scaffold so we will write one here. Please note that the test scaffold IS NOT PART OF THE SOLUTION.
5 3 4 7 2 1 9 2 7 9 9 7 main <<< strVal: [5, 3, 4, 7, 2, 1, 9] main <<< postOrderTraversal: 7 2 3 1 9 4 5 main <<< number of queries (m): 2 main <<< (7,9) sum: 28 main <<< (9,7) sum: 28 10 8 12 7 9 11 13 3 9 11 7 13 7 12 main <<< strVal: [10, 8, 12, 7, 9, 11, 13] main <<< postOrderTraversal: 7 9 8 11 13 12 10 main <<< number of queries (m): 3 main <<< (9,11) sum: 50 main <<< (7,13) sum: 50 main <<< (7,12) sum: 37 9 3 -1 6 -2 3 5 7 7 7 5 5 7 9 3 3 9 7 3 3 7 1 8 main <<< strVal: [9, 3, -1, 6, -2, 3, 5, 7] main <<< postOrderTraversal: 7 6 -2 3 3 5 -1 9 main <<< number of queries (m): 7 main <<< (7,5) sum: 29 main <<< (5,7) sum: 29 main <<< (9,3) sum: 11 main <<< (3,9) sum: 11 main <<< (7,3) sum: 27 main <<< (3,7) sum: 27 main <<< pVal: 1 NOT found in binary tree 3 5 1 6 2 0 8 null null 7 4 8 1 5 1 8 2 4 3 1 3 5 5 1 6 4 7 4 main <<< strVal: [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4] main <<< postOrderTraversal: 6 7 4 2 5 0 8 1 3 main <<< number of queries (m): 8 main <<< (1,5) sum: 9 main <<< (1,8) sum: 9 main <<< (2,4) sum: 6 main <<< (3,1) sum: 4 main <<< (3,5) sum: 8 main <<< (5,1) sum: 9 main <<< (6,4) sum: 17 main <<< (7,4) sum: 13 1 2 2 1 2 2 1 main <<< strVal: [1, 2] main <<< postOrderTraversal: 2 1 main <<< number of queries (m): 2 main <<< (1,2) sum: 3 main <<< (2,1) sum: 3 1 2 3 4 2 1 5 5 1 main <<< strVal: [1, 2, 3, 4] main <<< postOrderTraversal: 4 2 3 1 main <<< number of queries (m): 2 main <<< qVal: 5 NOT found in binary tree main <<< pVal: 5 NOT found in binary tree 1 3 5 7 9 11 13 -1 -2 -3 -4 -5 -6 -7 -8 3 7 -8 -8 7 -1 -8 main <<< strVal: [1, 3, 5, 7, 9, 11, 13, -1, -2, -3, -4, -5, -6, -7, -8] main <<< postOrderTraversal: -1 -2 7 -3 -4 9 3 -5 -6 11 -7 -8 13 5 1 main <<< number of queries (m): 2 main <<< (7,-8) sum: 21 main <<< (-8,7) sum: 21 1 3 5 7 9 11 13 -1 -2 -3 -4 -5 -6 -7 -8 1 -4 -4 main <<< strVal: [1, 3, 5, 7, 9, 11, 13, -1, -2, -3, -4, -5, -6, -7, -8] main <<< postOrderTraversal: -1 -2 7 -3 -4 9 3 -5 -6 11 -7 -8 13 5 1 main <<< number of queries (m): 1 main <<< (-4,-4) sum: -4
We have several test cases. Each test case describes a binary tree and a number of queries each specifying two nodes which we will use to call the function of interest.
Our test code seems to take multiple input lines. The first line contains a set of integers which represent an ordered list of nodes. The second input line contains the number of queries we will issue. For each query we will have two nodes for which our function of interest will compute the sum between them.
In this case we have 2 queries. The first with nodes 7 and 9 and the second with nodes 9 and 7. If all works well, both queries should return the same value, and it seems to do so.
Based on the previous diagram of the binary tree, we need to sum the values of nodes 7, 3, 5, 4 and 9. This implies 7 + 3 + 5 + 4 + 9 = 28. It seems that both queries are returning the correct values.
There are several test cases. You might want to take a look and make sure that you can follow what we need to do.
The problem did not provide a class for the TreeNode. We will use the following:
/**
* Auxiliary class to build the binary tree.
*/
class TreeNode {
// **** members ****
int val;
TreeNode left;
TreeNode right;
// **** constructor ****
TreeNode(int x) { val = x;}
}
Each node will be as simple as possible. Each node will hold an integer value and a right and left child which may or may not be `null`. Our constructor will receive an integer value and will return a node with `null` children. That is all we need in the TreeNode class.
/**
* Test scaffold.
* @throws InterruptedException
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws InterruptedException, NumberFormatException, IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the node values and place them in an array of strings ****
String strVal[] = br.readLine().trim().split(" ");
// ???? ????
System.out.println("main <<< strVal: " + Arrays.toString(strVal));
// **** root for the binary tree ****
TreeNode root = null;
// **** populate the binary tree ****
root = insertLevelNode(strVal, root, 0);
// ???? print the binary tree in post order traversal ????
System.out.print("main <<< postOrderTraversal: " + postOrderTraversal(root, new StringBuilder())+ "\n");
// **** get the number of queries ****
int m = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< number of queries (m): " + m);
// ***** loop once per query ****
for (int i = 0; i < m; i++) {
// **** read p and q ****
String[] pAndQ = br.readLine().trim().split(" ");
// **** convert to integer ****
int pVal = Integer.parseInt(pAndQ[0]);
// **** convert to integer ****
int qVal = Integer.parseInt(pAndQ[1]);
// **** find node p in the binary tree ****
TreeNode p = find(root, pVal);
if (p == null) {
System.out.println("main <<< pVal: " + pVal + " NOT found in binary tree");
continue;
}
// **** find node q in the binary tree ****
TreeNode q = find(root, qVal);
if (q == null) {
System.out.println("main <<< qVal: " + qVal + " NOT found in binary tree");
continue;
}
// // **** find the LCA of p and q ****
// TreeNode lca = lowestCommonAncestor(root, p, q);
// // **** display the LCA ****
// System.out.println("main <<< lowestCommonAncestor: (" + pVal + "," + qVal + ") lca: " + lca.val);
// // **** find the LCA of p and q (second attempt; ended being the same as previous) ****
// lca = lcaPostOrder(root, p, q);
// // **** display the LCA ****
// System.out.println("main <<< lcaPostOrder: (" + pVal + "," + qVal + ") lca: " + lca.val);
// **** sum node values between p and q and display result ****
System.out.println("main <<< (" + p.val + "," + q.val + ") sum: " +
sumNodes(root, new TreeNode[] {p}, new TreeNode[] {q}));
}
// **** close buffered reader ****
br.close();
}
Our test scaffold is as simple as we need. We start by reading the first input line and putting the integer numbers in a String[] array. We do so because a utility I wrote a few years ago is able to take `null` values to represent `null` children. Note that our test scaffold displays the String[] array `strVal` so we can verify that we were able to generate an array which will be used to create and populate a binary tree. Please note that generating the binary tree IS NOT PART OF THE SOLUTION. Our function of interest will be called with a binary tree and how it is created is out of the scope of this problem.
Our test scaffold then reads the int `m` which holds the number of queries we will be asked to process. The value of `m` is then displayed so we can verify that all is well so far.
Our test code enters a loop which should process one query at a time.
The loop reads the values of the `p` and `q` nodes. It then finds the associated nodes in the binary tree. If the values are not available as nodes in the binary tree, a message is displayed and the query is ignored.
Following is a set of commented out statements. Such code is not relevant for our solution. I left it for development and testing. In production it is not a good idea to leave code commented out. It should be removed.
The last line in the loop calls the function of interest with the two nodes and returns the sum of the values in the nodes of interest.
Please note that the `find` function used to look up the `p` and `q` nodes in the binary tree IS NOT PART OF THE SOLUTION.
This is a good time to stop further development and think about what we need to do to get the results we need to return by our function of interest.
It was my opinion that the problem could be solved using some type of binary tree traversal with modifications. I suggested using a post order tree traversal.
We could possibly have figured the LCA (Least Common Ancestor) for the two nodes and the sum in a single pass. We will go with two separate functions.
/**
* Sum the node values between specified nodes in the binary tree.
*
* o Gets LCA (Lowest Common Ancestor) node.
* o Computes sum of node values between p and q.
*
* !!! This is the function of interest !!!
*
* Execution: O(n) - Space: O(1)
*/
static int sumNodes(TreeNode root, TreeNode[] p, TreeNode[] q) {
// **** get the LCA between specified nodes - O(n)****
TreeNode lca = lcaPostOrder(root, p[0], q[0]);
// **** get the sum of the node values between specified nodes - O(n) ****
int sum = lca.val + rangeSum(lca, p, q);
// **** return sum ****
return sum;
}
The `lcaPostOrder` function returns the LCA node. Once we have the node we will call a second function named `rangeSum` which implements a separate post order tree traversal to compute the sum of the values of the nodes between `p` and `q`.
Please take a look at the comments section of this function. Looks like our implementation will run in O(n) time.
/**
* Finds and returns the LCA (Lowest Common Ancestor) node
* in the specified binary tree.
* Modified post order traversal recursive call.
*
* Execution: O(n) - Space: O(1)
*/
static TreeNode lcaPostOrder(TreeNode root, TreeNode p, TreeNode q) {
// **** base case ****
if ((root == null) || (root == p) || (root == q)) return root;
// **** visit the left child ****
TreeNode left = lcaPostOrder(root.left, p, q);
// **** visit the right child ****
TreeNode right = lcaPostOrder(root.right, p, q);
// **** p and q in the current root of the binary tree ****
if ((left != null) && (right!= null)) return root;
// **** p or q found but not both ****
if (left != null)
return left;
else
return right;
}
This function which uses a modified post order tree traversal is a recursive call. We first visit the left child and then the right child. If one of the nodes of interest is in the current path we return it to the caller. Since our test scaffold made sure that `p` and `q` are in the binary tree we will always be able to find them.
/**
* Given the root node of a binary tree and two nodes,
* return the sum of values of all nodes between p and q (inclusive).
*
* Modified post order traversal recursive call.
*
* Execution: O(n) - Space: O(1)
*/
static int rangeSum(TreeNode root, TreeNode[] p, TreeNode[] q) {
// **** base case ****
if (root == null) return 0;
// **** initialize sum ****
int sum = 0;
// **** traverse left tree ****
if (root.left != null)
sum += rangeSum(root.left, p, q);
// **** traverse right tree ****
if (root.right != null)
sum += rangeSum(root.right, p, q);
// **** update sum, p and q (as needed) ****
if (root.left != null && root.left == p[0]) {
sum += root.left.val;
p[0] = root;
}
else if (root.left != null && root.left == q[0]) {
sum += root.left.val;
q[0] = root;
}
if (root.right != null && root.right == p[0]) {
sum += root.right.val;
p[0] = root;
}
else if (root.right != null && root.right == q[0]) {
sum += root.right.val;
q[0] = root;
}
// **** return sum ****
return sum;
}
The `rangeSum` function which is also based on a post order tree traversal algorithm, checks the right and then the left child trees. If needed it updates the sum and the values for `p` and / or `q`. This is the reason we used a couple of arrays to wrap the `p` and `q` nodes. In Java arguments are passed by value unless it is a collection. We have used this array technique in multiple posts in this blog.
That is the implementation of the function of interest.
Before we start the implementation of the two functions that make up the solution, we could perform a post order tree traversal on the binary tree to help us visualize our algorithm,
/**
* Perform a post order traversal of a binary tree.
*
* !!! NOT PART OF SOLUTION !!!
*/
static public StringBuilder postOrderTraversal(TreeNode root, StringBuilder sb) {
if (root != null) {
// **** visit left child ****
postOrderTraversal(root.left, sb);
// **** visit right child ****
postOrderTraversal(root.right, sb);
// **** visit root ****
sb.append(root.val + " ");
// **** return ****
return sb;
} else return null;
}
I thought it would be nice to have such a handy function around. Our test scaffold makes a call to this function to display the sequence of nodes during a post order tree traversal.
Please note that we first thought about what to do. We then implemented the two functions we needed. If we would have more time we could attempt to condense the two functions into one. The result would be more complex and harder to maintain. I like functions that work and are as simple as possible to maintain.
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 websites (i.e., HackerRank, LeetCode). In this case you are out of luck. That said; if you find this problem on a web site, please let me know. Would like to compare it to what we have written.
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 / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John