Sum of Nodes Between Two Nodes in Binary Tree

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 &lt;&lt;&lt; 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 &lt;&lt;&lt; postOrderTraversal: " + postOrderTraversal(root, new StringBuilder())+ "\n");

        // **** get the number of queries ****
        int m = Integer.parseInt(br.readLine().trim());

        // ???? ????
        System.out.println("main &lt;&lt;&lt; number of queries (m): " + m);

        // ***** loop once per query ****
        for (int i = 0; i &lt; 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 &lt;&lt;&lt; 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 &lt;&lt;&lt; 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 &lt;&lt;&lt; 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 &lt;&lt;&lt;         lcaPostOrder: (" + pVal + "," + qVal + ") lca: " + lca.val);


            // **** sum node values between p and q and display result ****
            System.out.println("main &lt;&lt;&lt; (" + 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

Values From List of Lists

Good day! I am approaching the end of my workday. My wife is in the kitchen preparing chocolate frosting for a chocolate cake she baked this morning. We were going to have a piece after lunch, but she was busy and did not get to the frosting.

Yesterday evening my wife and I watched the film No Time To Die which is the last James Bond movie with Daniel Craig. I am a 007 fan. Growing up I read all the novels by Ian Fleming who created the James Bond character. I have watched most of the James Bond  films on opening night. This time I decided to wait for the film to be streamed from home.

Of course, there were a few books by Ian Fleming but there are much more films. In other words, most of the films are not based on the original books.

The last two films with Daniel Craig are Spectre and No Time To Die. I did not like Spectre at all. In my rankings it was the worst James Bond film at the time. After watching the new release, I can say that I did not like it either. I would rank it a small notch above the previous movie.

I have not much to say about Daniel Craig. As an actor he can help the delivery of the script, but that is it. If the story and script are not good, the film will follow. Daniel Craig has grown too old to play the 007 role. This is why No Time To Die was the last James Bond film for him.

The original character of James Bond was not represented in this film. The film was slow and his feelings were out of character. The movie was about 2.75 hours in length. To be honest, towards the end I was checking my watch to estimate how much of the movie was left.

There is a film named Knives Out with Daniel Craig and one of the Bond girls Ana de Armas. My wife and I have watched that film a few times. The plot and delivery by most actors is right on. The same cannot be said about No Time to Die.

If you are a fan of James Bond as I am, you must watch the film and then make up your own mind. The taste in people regarding films is hard to quantify. Many times we watch a movie highly rated and it turns out to be a disaster. Not too many times have we experienced the opposite.

On a side note, I was not able to finish this post yesterday. Will complete it right now. Continue reading “Values From List of Lists”

Permutation in String

Good morning! Hope you had a nice weekend. My wife and I did. We did some shopping, visited our son, and baked. For some reason last winter we did little baking. Yesterday morning after completing a two-hour block in my home office, I went up, prepared coffee and sat with my wife to chat. The subject of baking came up. Baking is both knowledge and art. In general when cooking or baking we tend not to follow recipes. Yesterday we collected the ingredients for raisin cinnamon bread around 09:00 AM. I got the dough ready around 10:00 AM. The dough proofed for a few hours and early afternoon, while my wife was preparing an avocado with tomatoes and roast beef salad, I buttered four bread molds, poured in the bread batter, waited for about 15 minutes (should be  an hour), and baked the cinnamon raisin bread. It turned out very good, but next week, I will let the bread proof for an hour in the molds. While the bread was still hot, we had two slices each with soft butter and grape jelly made by our daughter in law. It was delicious and to be honest with you, it does not require much work. Continue reading “Permutation in String”

Remove the Nth Node From End of List

Happy Friday! It is a typical fall Friday in the Twin Cities of Minneapolis and St. Paul. When I woke up this morning the outside temperature was 38F. The forecasted high for the day is 56F. Tomorrow the forecasted high temperature will be 67F. Will check with my wife if we will grill outside. Not too many grilling days left this year.

Earlier today I read the article Big whales eat 3 times as much as previously thought, which means killing them for food and blubber is even more harmful to the environment by Marianne Guenot. I also read a different article on the same subject titled The Enormous Hole That Whaling Left Behind by Ed Yong. Both articles are in agreement with the research and published papers. As humans, the idea of fertilizing the waters in specific areas seems to be a good thing to do now that the amounts of iron to use have been accurately estimated. Perhaps in the next few decades the oceans will see whales in the numbers they existed 60 years ago. Continue reading “Remove the Nth Node From End of List”

Counting Bits

It is Friday and not a hot as it has been in the couple last weeks. The forecast calls for a high around 88F. We will see if the forecast matches the observed temperatures for the day.

The cleaning lady and crew are expected today. Apparently last week she had some issues which ended in a no show.

Due to the fact that I usually talk on Fridays at 07:00 AM with a friend that we met while attending elementary school, my wife and I decided to postpone our daily walk to around lunch. It turns out that my friend had to get up quite early today and travel for business for about two hours. We both are morning people but getting up around 03:00 AM to chat is not acceptable.

Since the cleaning crew will be leaving around lunch time, and my wife and I will go out for a walk, she will not have time to cook lunch which is our main meal of the day. On our way back I will pick up a bag of Asian food from Trader Joe’s which we keep in the outside fridge. Hopefully it will be Kung Pao Chicken. It is our favorite. That said; we typically alter the meal to our taste by adding different things (i.e., chicken broth, unsalted peanuts).

Yesterday I read a very interesting article on IEEE SPECTRUM titled How Software Is Eating the Car. The complexity of software and the amount of features depending on it is growing exponentially. I have had the opportunity to owning several German made cars and have experienced the increase of features and hardware referenced in the article.

Continue reading “Counting Bits”

Grid Traveler – Tabulation

It is another nice and hot spring day in the Twin Cities of Minneapolis and St. Paul. Yesterday after work my wife and I headed to the bank. On our way back I noticed that the temperature had gone up to 99F.

Earlier today after breakfast my wife and I went out on our daily walk. There were more people than usual. We stopped to talk with a neighbor that was also out and about. She likes to walk at a good pace. She was covered in sweat.

The forecasted temperatures for the next couple weeks will are in the mid 80s to the mid 90s. During lunch time the temperature went up to 93F. In general the high temperature for the day occurs around 05:00 PM.

A couple weeks ago we were talking with a couple of neighbors. They mentioned that some of our plants in the front yard were dead. Today during lunch the company that handles plants and lawns stopped by to remove and replace all the dead shrubs.

On a separate note, things are not going well with the vote counting process. There seems to be a lot of cheating going on. It seems that the candidate that represents communism and terrorism will get elected president. The economy has come to a standstill. The Peruvian currency is devaluating.

In addition the candidate from the left is instigating people to go after the upper and middle classes. Hope this things is resolved peacefully in the next few days. Continue reading “Grid Traveler – Tabulation”

Movies on Flight

Good day! It is a Friday in the month of May. The forecast called for rain and thunderstorms. We only received some rain. It is good to have some rain because things were starting to dry up. When vegetation dries up it may catch on fire.

In this post I will attempt to solve two flavors of the same problem. I believe one can create a few more problems by changing just a few words in the requirement. This will become clear as we read the requirements and describe the differences.

I found this problem named Movies on Flight in the LeetCode web site. Apparently Amazon has been using different versions on some of their technical assessments. Continue reading “Movies on Flight”

Symmetric Tree

Good morning gals and guys! Hope you day has started on the right note. Today in the Twin Cities of Minneapolis and St. Paul we are expecting a high temperature of 67F and the day is sunny. Starting today the two-week forecast shows high temperatures in the upper 60’s to mid to lower 70’s. All looks nice, but we are somewhat low on precipitation. From my backyard I can see a small pond with very low water levels. Hopefully farmers are receiving enough rain to have a good crop this fall.

This morning I watched a session from AWS Summit Online. The session is named “Amazon DynamoDB: Untold stories of databases in a serverless world” by Angela Timofte. She is a data platform manager with Trustpilot. What called my attention were a set of points she brought up which illustrates how important is to allow your technical staff to experiment, learn and make mistakes. Such approach has helped the company move from MySQL to MongoDB and currently to DynamoDB. What is more important, the company currently uses about ten different database engines to store different types of data. They are using the right tools for the jobs (one size does not fit all). If you get a chance take a look at the 22 minute presentation here. Continue reading “Symmetric Tree”