It is 11:20 AM CDT and the garage door repair technicians have not shown up yet. They mentioned they were going to be here first thing in the morning. The problem is that the door is jammed and we are not able to drive our vehicles. This will definitely be the last time we use this company. I will post the name of the company in a future blog after the door is fixed. We are planning on calling someone else if the technicians do not show up in the next 40 minutes or so.
Believe it or not, @ 11:30 AM a technician showed up with the board. A cracked board started the issue about three weeks ago. I spent some time helping him open the door to some extent. I was able to move a car out. We have some freedom at this time. If the technician needs some help he will let us know. We still have our SUV in the garage but cannot make it through the door yet.
Last week I ran into the following problem / challenge which did not include a solution. I decided to tackle it using Java.
Take a look at the following diagram:
If you start at the root and traverse the tree down to the first leaf you will encounter the following values: 1, 0, and 1 which represent in binary 101 decimal 5. For the second leaf node we find 1, 0, and 0 which in binary 100 stands for decimal 4. Finally the path to the last node 1, 0 represents in binary 10 or 2 in decimal.
The challenge, if you wish to accept it, is to write a function that will return the sum of the leaf nodes, which in this case would be: 5 + 4 + 2 = 11 in decimal.
First we need to build the tree. To do so we may use the following code:
package canessa.tree.sum;
public class Solution {
public static void main(String[] args) {
// **** build the binary tree as illustrated here ****
BinaryTree tree = new BinaryTree(1); // was: 1
Node root = tree.getRoot();
// **** allocate nodes for the tree ****
Node n2 = new Node(0); // was: 0
Node n3 = new Node(1); // was: 1
Node n4 = new Node(0); // was: 0
Node n5 = new Node(0); // was: 0
// **** add nodes to the tree ****
tree.add(root, n2, ChildLocation.LEFT);
tree.add(root, n5, ChildLocation.RIGHT);
tree.add(n2, n3, ChildLocation.LEFT);
tree.add(n2, n4, ChildLocation.RIGHT);
// **** breadth first using queue ****
System.out.println("main <<< BFS:");
tree.BFS(root);
System.out.println();
// **** ****
int sum = tree.sumLeafs(root, 0);
System.out.println("main <<< sum: " + sum);
}
}
We first allocate the root and set its value to 1 (in binary). We then allocate the remaining nodes following the names used in the diagram and attach them to the tree.
To see if all is well so far, we perform a breadth first search.
Finally we compute the specified sum by calling the sumLeafs() method.
The output from Eclipse IDE console generated by this program follows:
main <<< BFS: 1 0 0 1 0 1 main <<< sum: 14
The root level contains the root node with value 1.
The next level down contains two nodes with values 0 and 0.
The third and last node contains the nodes with value 1, 0 and 1.
The results obtained from the program seem to match the results illustrated in the diagram.
Now let’s look at the Node class as illustrated by the following code:
package canessa.tree.sum;
public class Node {
// **** members ****
int value;
Node left;
Node right;
int currentSum;
Node parent;
int level;
/*
* constructor(s)
* Root level is zero (0).
*/
public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
this.level = 0;
}
/*
* Display the specified node.
*/
public void displayNode() {
System.out.println("value: " + value);
}
/*
* Generate a string with the contents of the node.
*/
public String toString() {
return "" + this.value;
}
}
Of interest are: value, left and right elements. The currentSum element is used to keep track of the sum of all bits from the root to the current node. For this example please disregard the parent and level nodes which are not used in our example. Please note that the currentSum keeps track of the position of the bits in the number.
Our last class BinaryTree follows:
package canessa.tree.sum;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/*
*
*/
enum ChildLocation {
LEFT,
RIGHT
}
/*
* Breadth first is a queue, depth first is a stack.
*/
public class BinaryTree {
// **** ****
private Node root;
/*
* constructor
*/
public BinaryTree(int value) {
Node root = new Node(value);
this.root = root;
}
/*
* return the root of the binary tree
*/
public Node getRoot() {
return this.root;
}
/*
* add a node to the binary tree
*/
public void add(Node parent, Node child, ChildLocation location) {
// **** set level in child node ****
child.level = parent.level + 1;
// **** insert the child at the specified location ****
if (location == ChildLocation.LEFT) {
parent.left = child;
} else {
parent.right = child;
}
}
/*
* in order traversal
* left - root - right
*/
public void inOrder(Node n) {
if (n != null) {
inOrder(n.left);
n.displayNode();
inOrder(n.right);
}
}
/*
* post order traversal
* left - right - root
*/
public void postOrder(Node n) {
if (n != null) {
inOrder(n.left);
inOrder(n.right);
n.displayNode();
}
}
/*
* pre order traversal
* root - left - right
*/
public void preOrder(Node n) {
if (n != null) {
n.displayNode();
inOrder(n.left);
inOrder(n.right);
}
}
/*
* This method implements a breadth-first search traversal of a binary tree.
* This method is not recursive.
* It displays all nodes at each level on a separate line.
*/
public void BFS(Node root) {
List<Node> currentQ = new LinkedList<Node>();
List<Node> nextQ = new LinkedList<Node>();
currentQ.add(root);
while (!currentQ.isEmpty()) {
Node n = currentQ.remove(0);
System.out.print(n.toString() + " ");
if (n.left != null)
nextQ.add(n.left);
if (n.right != null)
nextQ.add(n.right);
// **** check if end of current level ****
if (currentQ.isEmpty()) {
System.out.println();
currentQ = nextQ;
nextQ = new LinkedList<Node>();
}
}
}
/*
* Similar to BFS but using stacks.
* Does not seem to provide a known order.
*/
public void MysteryOrder(Node root) {
Stack<Node> currentS = new Stack<Node>();
Stack<Node> nextS = new Stack<Node>();
currentS.push(root);
while(!currentS.isEmpty()) {
Node n = currentS.pop();
System.out.print(n.toString() + " ");
if (n.left != null)
nextS.push(n.left);
if (n.right != null)
nextS.push(n.right);
// **** ****
if (currentS.isEmpty()) {
System.out.println();
currentS = nextS;
nextS = new Stack<Node>();
}
}
}
/*
*
*/
public void DFSInOrder(Node root) {
Stack<Node> s = new Stack<Node>();
Node n = root;
while ((n != null) || (s.size() > 0)) {
while (n != null) {
s.push(n);
n = n.left;
}
n = s.pop();
n.displayNode();
n = n.right;
}
}
/*
*
*/
public void DFSPostOrder(Node root)
{
Stack<Node> stack = new Stack<Node>();
stack.push(root);
Node prev = null;
while (!stack.isEmpty()) {
Node n = stack.peek();
if (prev == null || prev.left == n || prev.right == n) {
if (n.left != null)
stack.push(n.left);
else if (n.right != null)
stack.push(n.right);
else {
stack.pop();
n.displayNode();
}
} else if (n.left == prev) {
if (n.right != null)
stack.push(n.right);
else {
stack.pop();
n.displayNode();
}
} else if (n.right == prev) {
stack.pop();
n.displayNode();
}
prev = n;
}
}
/*
* Compute the sum of all intermediate nodes from the root to all leaf nodes.
*/
public int sumLeafs(Node t, int prevSum) {
// **** reached a leaf node ****
if ((t.left == null) &&
(t.right == null)) {
return (prevSum * 2) + t.value;
}
// **** returned from leaf nodes ****
int sum = 0;
// **** update the current sum ****
t.currentSum = (prevSum * 2) + t.value;
// **** have left child ****
if (t.left != null) {
sum += sumLeafs(t.left, t.currentSum);
}
// **** have right child ****
if (t.right != null) {
sum += sumLeafs(t.right, t.currentSum);
}
// **** ****
return sum;
}
}
The only method of interest is sumLeafs() which computes the value of the individual leaf branches, sums them up and returns the sum to the caller. Note that we also used the BFS() method to display the tree to make sure we built the binary tree as expected.
he 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 me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa