Binary Tree Sum

In this post we will develop a couple methods to collect some information from a binary tree. The first method will be the base, and the second will be an enhancement of the first.

The first requirement is:  given a binary tree with double values, compute the sum of all nodes in the tree.

The second requirement is:  given a binary tree with double values, compute the sum of all nodes whose values are in a specified range (e.g., [ 10.0 : 15.0 ]).

We will start by creating a GitHub repository which we will name BinaryTreeSum. We will add a simple README.md file and will clone it so we can work with it in our Windows 10 computer. The solution will be in Java 8. We will use the Visual Studio Code IDE. Of course you can use whichever IDE you prefer.

# **** contents of the workspace before cloning repository from GitHub ****
C:\Users\John>cd workspace7

C:\Users\John\workspace7>dir
02/22/2020  07:08 AM    <DIR>          .
02/22/2020  07:08 AM    <DIR>          ..
01/30/2020  01:32 PM    <DIR>          .metadata
01/31/2020  09:02 AM    <DIR>          .vscode
01/05/2020  07:15 AM    <DIR>          3DSurfaceArea
01/06/2020  11:52 AM    <DIR>          AlmostSorted
02/06/2020  07:16 AM    <DIR>          AndProduct
01/24/2020  12:49 PM    <DIR>          AStarSearch
12/05/2019  01:23 PM    <DIR>          BiggerIsGreater
02/14/2020  03:00 PM    <DIR>          Cipher
12/22/2019  08:35 AM    <DIR>          DeterminingDNAHealth
01/08/2020  07:07 AM    <DIR>          EmasSupercomputer
02/12/2020  02:46 PM    <DIR>          FirstDuplicate
02/03/2020  09:07 AM    <DIR>          FlippingBits
02/20/2020  08:14 AM    <DIR>          FullCountingSort
02/16/2020  09:09 AM    <DIR>          GitHubTest
01/31/2020  02:57 PM    <DIR>          guava-mini
01/31/2020  10:44 AM    <DIR>          HelloMaven
02/17/2020  10:43 AM         2,339,925 ij.jar
02/17/2020  10:52 AM    <DIR>          ImageJ
02/22/2020  07:45 AM    <DIR>          JavaStreams
02/04/2020  02:04 PM    <DIR>          JumpingOnTheClouds
01/23/2020  08:05 AM    <DIR>          LarrysArray
12/03/2019  04:26 PM    <DIR>          MatrixLayerRotation
02/03/2020  10:42 AM    <DIR>          MiniMaxSum
01/25/2020  08:07 AM    <DIR>          PriorityQ
01/30/2020  01:42 PM    <DIR>          rtree2
02/03/2020  01:44 PM    <DIR>          SansaXOR
01/19/2020  09:16 AM    <DIR>          StacksReverseOrder
02/19/2020  08:08 AM    <DIR>          SumOfTwo
01/04/2020  07:51 AM    <DIR>          TheGridSearch
12/11/2019  10:09 AM    <DIR>          ToTrieOrNotToTrie

# **** clone the BinaryTreeSum git repo ****
C:\Users\John\workspace7>git clone https://github.com/JohnCanessa/BinaryTreeSum.git
Cloning into 'BinaryTreeSum'...
remote: Enumerating objects: 3, done.
remote: Counting objects: 100% (3/3), done.
remote: Compressing objects: 100% (2/2), done.
remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (3/3), done.

# **** updated directory ****
C:\Users\John\workspace7>dir
02/25/2020  02:03 PM    <DIR>          .
02/25/2020  02:03 PM    <DIR>          ..
01/30/2020  01:32 PM    <DIR>          .metadata
01/31/2020  09:02 AM    <DIR>          .vscode
01/05/2020  07:15 AM    <DIR>          3DSurfaceArea
01/06/2020  11:52 AM    <DIR>          AlmostSorted
02/06/2020  07:16 AM    <DIR>          AndProduct
01/24/2020  12:49 PM    <DIR>          AStarSearch
12/05/2019  01:23 PM    <DIR>          BiggerIsGreater
02/25/2020  02:03 PM    <DIR>          BinaryTreeSum        <===
02/14/2020  03:00 PM    <DIR>          Cipher
12/22/2019  08:35 AM    <DIR>          DeterminingDNAHealth
01/08/2020  07:07 AM    <DIR>          EmasSupercomputer
02/12/2020  02:46 PM    <DIR>          FirstDuplicate
02/03/2020  09:07 AM    <DIR>          FlippingBits
02/20/2020  08:14 AM    <DIR>          FullCountingSort
02/16/2020  09:09 AM    <DIR>          GitHubTest
01/31/2020  02:57 PM    <DIR>          guava-mini
01/31/2020  10:44 AM    <DIR>          HelloMaven
02/17/2020  10:43 AM         2,339,925 ij.jar
02/17/2020  10:52 AM    <DIR>          ImageJ
02/22/2020  07:45 AM    <DIR>          JavaStreams
02/04/2020  02:04 PM    <DIR>          JumpingOnTheClouds
01/23/2020  08:05 AM    <DIR>          LarrysArray
12/03/2019  04:26 PM    <DIR>          MatrixLayerRotation
02/03/2020  10:42 AM    <DIR>          MiniMaxSum
01/25/2020  08:07 AM    <DIR>          PriorityQ
01/30/2020  01:42 PM    <DIR>          rtree2
02/03/2020  01:44 PM    <DIR>          SansaXOR
01/19/2020  09:16 AM    <DIR>          StacksReverseOrder
02/19/2020  08:08 AM    <DIR>          SumOfTwo
01/04/2020  07:51 AM    <DIR>          TheGridSearch
12/11/2019  10:09 AM    <DIR>          ToTrieOrNotToTrie

# **** let's check what was downloaded ****
C:\Users\John\workspace7>cd BinaryTreeSum

C:\Users\John\workspace7\BinaryTreeSum>dir /A
02/25/2020  02:03 PM    <DIR>          .
02/25/2020  02:03 PM    <DIR>          ..
02/25/2020  02:03 PM    <DIR>          .git
02/25/2020  02:03 PM               173 README.md

We will clone our GitHub repository into my workspace7 folder. You can clone it to the folder of your choice. Once we have cloned the repo we will check the contents of the newly created folder.

10
11.0 7.1 15.2 5.3 8.4 12.5 18.6 3.7 6.8 13.9

n: 10
list: [11.0, 7.1, 15.2, 5.3, 8.4, 12.5, 18.6, 3.7, 6.8, 13.9]
sum: 102.5
inorder: 3.7 5.3 6.8 7.1 8.4 11.0 12.5 13.9 15.2 18.6

sum: 102.5
LEFT: 10.0 RIGHT: 15.0
sumInRange: 37.4

We will have to create a test scaffolding with some binary tree operations in order to get to the point we can call the two methods that are the object of this post.

We specify the number of elements we will pass for a test followed by the specified number of double values.

Just to make sure all is well, the program displays the number of values followed by a list holding the actual values. For sanity purpose we display the sum of all values followed by an inOrder traversal of the tree. This implies we will have to create the binary tree and the node which we will use to construct the tree.

We then will call the first method of interest. Note that the sum matches the sum of the values in the list.

We then display the range we will use for our test. The sum of the values in that range follows. I was going to generate such value from the list but will leave it as an exercise.


  /**
   * Test scaffolding.
   * 
   * @throws IOException
   */
  public static void main(String[] args) throws IOException {
    
    // **** open a buffered reader ****
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  
    // **** read the count of values to process ****
    int n = Integer.parseInt(bufferedReader.readLine());
  
    // ???? ????
    System.out.println("n: " + n);

    // **** read the values for the nodes and put them in a list ****
    List<Double> list = Stream.of(bufferedReader.readLine().split(" "))
                          .mapToDouble(Double::parseDouble)
                          .boxed()
                          .collect(Collectors.toList());

    // ???? ????
    System.out.println("list: " + list.toString());

    // **** instantiate a new empty tree ****
    BTree tree = new BTree();

    // *** loop inserting nodes into the tree ****
    double sum = 0.0;
    for (int i = 0; i < list.size(); i++) {

      // ???? ????
      sum += list.get(i);

      // **** insert this value into the binary tree ****
      tree.insert(tree.root, list.get(i));
    }

    // ???? ????
    System.out.println("sum: " + sum);

    // ???? inorder traversal of the tree ????
    System.out.print("inorder: ");
    tree.inorder(tree.root);
    System.out.println("\n");

    // **** sum the values of the nodes in the tree *****
    sum = tree.sum(tree.root);
    System.out.println("sum: " + sum);

    // **** specify range [LEFT : RIGHT] ****
    final double LEFT = 10.0;
    final double RIGHT = 15.0;
  
    // ???? ????
    System.out.println("LEFT: " + LEFT + " RIGHT: " + RIGHT);

    // **** sum the values of the nodes in the tree with inclusive constraints ****
    double sumInRange = tree.sumInRange(tree.root, LEFT, RIGHT);
    System.out.println("sumInRange: " + sumInRange);

    // **** close the buffered reader ****
    bufferedReader.close();
  }

We open a buffered reader and read the count. We then read the next line, convert them to doubles and return the resulting binary values in a list.

We then create an empty binary tree. We then loop through the list inserting the double values. We also generate a sum of the values in the list to verify that our binary tree method that computes the sum of all nodes returns the same value. The value is then displayed.

Just to verify that our tree is in good shape, we call an inOrder traversal method which should display all the values in ascending order. If that fails, we could have an issue with the insertion or the tree traversal. In our case it seems that all is well.

We now call our sum() method and display the result. The sum match so that seems to have worked as expected.

We decide on two values to be used as a range which we will us to compute the sum of values in the same tree. With that on hand we invoke the sumInRange() method and display the results.

When all is done, we close the buffered reader.

/**
 * Node for the binary tree.
 */
public class Node {

  // **** members ****
  double value;
  Node  left;
  Node  right;

  /**
   * Constructor.
   */
  public Node(double value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

   /**
    * To string.
    */
  @Override
  public String toString() {
    return  "Node {" +
            " value: " + this.value + 
            "}";
  }
}

The Node class holds three members, one for the value and the other two as reference to the left and right children. We also implement the toString() method in case we need to display the contents of a Node.

 /**
   * Sum the values of all the nodes in the tree.
   * This is a recursive call.
   */
  public double sum(Node root) {

    // **** for starters ****
    double s = 0.0;

    // **** end condition ****
    if (root == null) {
      return 0.0;
    }

    // **** value of current node ****
    s = root.value;

    // **** process left tree ****
    if (root.left != null) {
      s += sum(root.left);
    }

    // **** process right tree ****
    if (root.right != null) {
      s += sum(root.right);
    }

    // **** return sum ****
    return s;
  }

This method computes the sum of the values of the binary tree. Note the method is recursive. When we call this method we initialize the sum. If the root is null we are done and we need to return a 0.0 value.

If we do not have a null root we get the value of the node and check if we have a left child. If we do, we recursively call the sum method using the left child. If we have a right child we call the sum method with the right child. Note that in both cases the returned value is added to the sum.

When all is said and done we return the sum of all nodes in our binary tree.

/**
   * Sum values in range in the specified tree.
   * This is a recursive call.
   */
  public double sumInRange(Node root, double left, double right) {

    // **** for starters ****
    double s = 0.0;

    // **** end condition ****
    if (root == null) {
      return 0.0;
    }

    // **** add the value of current node (if needed) ****
    if ((root.value >= left) && (root.value <= right)) {
      s += root.value;
    }

    // **** add value from left node (if needed) ****
    if (root.left != null) {
      s += sumInRange(root.left, left, right);
    }

    // **** add value of right node (if needed) ****
    if (root.right != null) {
      s += sumInRange(root.right, left, right);
    }

    // **** return the sum ****
    return s;
  }

This method is quite similar to the sum() method we implemented in this class. The difference is that we are passing two additional parameters which we will use to narrow the scope of our sum.

As before, we need to initialize the sum. We then check for the end condition. If the root is not null, we add the value of the node if it is in the specified range.

We now check the left node and if available we call the sumInRange() method with the left child. If the right node is available, we repeat with the right child. As before, we need to add the returned values to the sum. When all is said and done the method returns the sum of the nodes with the specified constraints.

import java.util.List;

/**
 * Implements a binary tree of type Node.
 */
public class BTree {

  // **** root for a binary tree ****
  Node root = null;

  /**
   * Constructor without values.
   */
  public BTree () {
    this.root = null;
  }

  /**
   * Constructor with list of values.
   */
  public BTree(Node root, List<Double> list) {

    // ***** loop inserting nodes into the tree ****
    for (int i = 0; i < list.size(); i++) {
      insert(root, list.get(i));
    }

  }

  /**
   * Insert value into tree.
   * This is a recursive method.
   */
  public void insert(Node root, double v) {

    // **** add this node as the root of the tree ****
    if (root == null) {
      root = new Node(v);
      this.root = root;
      return;
    }

    // **** deal with the left child ****
    if (v <= root.value) { if (root.left == null) { root.left = new Node(v); return; } else { insert(root.left, v); } } // **** deal with the right child **** else { if (root.right == null) { root.right = new Node(v); return; } else { insert(root.right, v); } } } /** * In-order tree traversal. * This is a recursive call. */ public void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.value + " "); inorder(root.right); } } /** * Sum the values of all the nodes in the tree. * This is a recursive call. */ public double sum(Node root) { // **** for starters **** double s = 0.0; // **** end condition **** if (root == null) { return 0.0; } // **** value of current node **** s = root.value; // **** process left tree **** if (root.left != null) { s += sum(root.left); } // **** process right tree **** if (root.right != null) { s += sum(root.right); } // **** return sum **** return s; } /** * Sum values in range in the specified tree. * This is a recursive call. */ public double sumInRange(Node root, double left, double right) { // **** for starters **** double s = 0.0; // **** end condition **** if (root == null) { return 0.0; } // **** add the value of current node (if needed) **** if ((root.value >= left) && (root.value <= right)) {
      s += root.value;
    }

    // **** add value from left node (if needed) ****
    if (root.left != null) {
      s += sumInRange(root.left, left, right);
    }

    // **** add value of right node (if needed) ****
    if (root.right != null) {
      s += sumInRange(root.right, left, right);
    }

    // **** return the sum ****
    return s;
  }
}

This is the entire class for the binary tree. It has a couple constructors. They both call the insert() method.

The insert() method check is the tree is empty. If so creates a node with the specified value and assigns it to the root of the tree.

We now check if our value is less than or equal to the value in the current node. If the child is null we create a new node and assign it as a child. By calling the insert() method we can repeat the process with the child node. Sooner or later we will reach a leaf node and we will create a new Node, set the value and assign it to the current node.

The inOrder() method is used to traverse the binary tree to make sure things look good. If all is well the values for all the nodes will be displayed in ascending order.

We already discussed the last two methods which are at the core of the objective of this post.

We seem to be done so it is time to push our code to our GitHub repository.

# **** get status ****
C:\Users\John\workspace7\BinaryTreeSum>git status
On branch master
Your branch is up to date with 'origin/master'.

Untracked files:
  (use "git add <file>..." to include in what will be committed)

        BTree.java
        Node.java
        Solution.java

nothing added to commit but untracked files present (use "git add" to track)

# **** add the tree files to be committed ****
C:\Users\John\workspace7\BinaryTreeSum>git add BTree.java

C:\Users\John\workspace7\BinaryTreeSum>git add Node.java

C:\Users\John\workspace7\BinaryTreeSum>git add Solution.java

# **** check status ****
C:\Users\John\workspace7\BinaryTreeSum>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes to be committed:
  (use "git reset HEAD <file>..." to unstage)

        new file:   BTree.java
        new file:   Node.java
        new file:   Solution.java

# **** commit the files ****
C:\Users\John\workspace7\BinaryTreeSum>git commit -m "initial implementation"
[master f0ef8b8] initial implementation
 3 files changed, 246 insertions(+)
 create mode 100644 BTree.java
 create mode 100644 Node.java
 create mode 100644 Solution.java

# **** get status ****
C:\Users\John\workspace7\BinaryTreeSum>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)

nothing to commit, working tree clean

# **** push the changes to GitHub ****
C:\Users\John\workspace7\BinaryTreeSum>git push origin master
Enumerating objects: 6, done.
Counting objects: 100% (6/6), done.
Delta compression using up to 8 threads
Compressing objects: 100% (5/5), done.
Writing objects: 100% (5/5), 2.05 KiB | 1.02 MiB/s, done.
Total 5 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/BinaryTreeSum.git
   89d01c3..f0ef8b8  master -> master

# **** check status ****
C:\Users\John\workspace7\BinaryTreeSum>git status
On branch master
Your branch is up to date with 'origin/master'.

nothing to commit, working tree clean

# **** display the log ****
C:\Users\John\workspace7\BinaryTreeSum>git log master
commit f0ef8b8ae0b4c058c827d8bd6203913dd752e50c (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Wed Feb 26 08:53:23 2020 -0600

    initial implementation

commit 89d01c3e38dab0548f30617322f0583dcd0c201c
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date:   Tue Feb 25 14:01:14 2020 -0600

    Create README.md

We add the tree files so they can be committed. We commit the tree files and then push our code to GitHub. The log indicates that all has worked as expected.

I went to my GitHub repository and the additional files with the proper contents were uploaded. All seems to be fine.

I need to create the actual post on WordPress and when I have a URL I will update the README.md file directly in the GitHub repo.

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, refresh your knowledge and enhance your developer toolset!

One last thing, thanks to all 328 subscribers to my blog!!!

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.