I did not find this problem on a website. The requirements came up during a conversation with a software engineer. I wish I could have taken some notes but I did not. The problem had a single diagram of a sample general tree and there was no class definition for the nodes.
We are given a general binary three in which a node may have none, one or more children. In addition each node has an integer value. The values may repeat. Our tasks if to come up with a function that will display the leaf nodes for which the sum of all node values in the path from the root add up to a defined target.
As far as I can remember that was the gist of the problem.
The following diagram represents one of the test cases I made.
We start traversing the tree from the root node. The initial sum is 1. The node below it increases the sum up to 1 + 3 = 4. The node below it increases the sum up to 4 + 3 = 7. The branch to the left increases the sum to 7 + 1 = 8 and the center node increases the sum up to 8 + 2 = 10 which is equal to the target sum and the node is a leaf in our tree.
If we go back to the node from which we branched left, we can move down and the sum increases 7 + 2 = 9. We now take the left branch and the sum goes up to 9 + 1 = 10 which is equal to the target sum and the node is also a leaf in our tree.
These are the only leaf nodes whose sums of nodes from the root add up to 10.
I like to develop software from the bottom up. In this case we will have to develop a test scaffold which will read the input to define the general binary tree and populate it. At that point our test scaffold should call the function of interest which will need as arguments the root of the tree, and the target value for the sum. The function should return a string with the representation of the resulting nodes. Back to our diagram, we should print the same two leaf nodes we have flagged on our diagram.
1 10,[2,34,56,100] main <<< lines: 1 main <<< strLst(0) ==>10,[2,34,56,100]<== <<< l: 0 line ==>10,[2,34,56,100]<== main <<< levelOrder root: 10 2 34 56 100 2 10,[2,34,56,100] 2,[77,88],34,[],56,[1],100,[2,8,9] main <<< lines: 2 main <<< strLst(0) ==>10,[2,34,56,100]<== main <<< strLst(1) ==>2,[77,88],34,[],56,[1],100,[2,8,9]<== <<< l: 0 line ==>10,[2,34,56,100]<== <<< l: 1 line ==>2,[77,88],34,[],56,[1],100,[2,8,9]<== main <<< levelOrder root: 10 2 34 56 100 77 88 1 2 8 9 2 1,[2,3,4,5] 2,[6,7],3,[],4,[8],5,[9,10,11] main <<< lines: 2 main <<< strLst(0) ==>1,[2,3,4,5]<== main <<< strLst(1) ==>2,[6,7],3,[],4,[8],5,[9,10,11]<== <<< l: 0 line ==>1,[2,3,4,5]<== <<< l: 1 line ==>2,[6,7],3,[],4,[8],5,[9,10,11]<== main <<< levelOrder root: 1 2 3 4 5 6 7 8 9 10 11 1 1,[1,2] main <<< lines: 1 main <<< strLst(0) ==>1,[1,2]<== <<< l: 0 line ==>1,[1,2]<== main <<< levelOrder root: 1 1 2 2 1,[1,2] 1,[2,3],2,[1,2,3] main <<< lines: 2 main <<< strLst(0) ==>1,[1,2]<== main <<< strLst(1) ==>1,[2,3],2,[1,2,3]<== <<< l: 0 line ==>1,[1,2]<== <<< l: 1 line ==>1,[2,3],2,[1,2,3]<== main <<< levelOrder root: 1 1 2 2 3 1 2 3 3 1,[2,3] 2,[4,5],3,[6,7,8] 4,[],5,[9,10,11],6,[],7,[12,13,14],8,[15,16,17] main <<< lines: 3 main <<< strLst(0) ==>1,[2,3]<== main <<< strLst(1) ==>2,[4,5],3,[6,7,8]<== main <<< strLst(2) ==>4,[],5,[9,10,11],6,[],7,[12,13,14],8,[15,16,17]<== <<< l: 0 line ==>1,[2,3]<== <<< l: 1 line ==>2,[4,5],3,[6,7,8]<== <<< l: 2 line ==>4,[],5,[9,10,11],6,[],7,[12,13,14],8,[15,16,17]<== main <<< levelOrder root: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 4 1,[1,1,2] 1,[2,3],1,[2],2,[3,4,5] 2,[],3,[],2,[1,2,3],3,[],4,[],5,[] 1,[1,2,3],2,[4,5,6],3,[7,8,9] main <<< lines: 4 main <<< strLst(0) ==>1,[1,1,2]<== main <<< strLst(1) ==>1,[2,3],1,[2],2,[3,4,5]<== main <<< strLst(2) ==>2,[],3,[],2,[1,2,3],3,[],4,[],5,[]<== main <<< strLst(3) ==>1,[1,2,3],2,[4,5,6],3,[7,8,9]<== <<< l: 0 line ==>1,[1,1,2]<== <<< l: 1 line ==>1,[2,3],1,[2],2,[3,4,5]<== <<< l: 2 line ==>2,[],3,[],2,[1,2,3],3,[],4,[],5,[]<== <<< l: 3 line ==>1,[1,2,3],2,[4,5,6],3,[7,8,9]<== main <<< levelOrder root: 1 1 1 2 2 3 2 3 4 5 1 2 3 1 2 3 4 5 6 7 8 9
We have some early test cases in this screen capture. Each test case is separated from the next by two blank lines.
The first line contains the number of levels in our tree. The following lines describe the nodes in a level. The first integer contains the node value. The following list holds the references to the children nodes.
Our test scaffold seems to read the first input line and extract the number of lines in our tree. The value is then displayed. The test code then reads the first and in this case only level for our tree. The input line is displayed to make sure all is well so far.
During the parsing of the input data, some function that generates and populates the tree displays the input line it is working on. Please note that the code used to generate, populate and traverse the general trees IS NOT PART OF THE SOLUTION. We could just write code to populate a specific single tree or take the time to define a format for the input data, and then develop code to create and populate any tree. I decided to take additional time to develop the second approach.
Back to the first test case, after the tree is created and populated we make a call to a function that displays the tree in level order. Our tree has a root node with value 10 and four child nodes with values 2, 34, 56 and 100. Such nodes do not have offspring.
I also wish to point out that at this time all the test cases are to test to some extent that the test scaffold is able to generate a tree that we can use to develop our solution. So far all the code we have developed IS NOT PART OF THE SOLUTION.
10 4 1,[2,3,4] 2,[1,2],3,[3],4,[1,2,3] 1,[],2,[],3,[1,2,3],1,[],2,[],3,[] 1,[1,2,3],2,[1,2,3],3,[1,2,3] main <<< sum: 10 main <<< lines: 4 main <<< strLst(0) ==>1,[2,3,4]<== main <<< strLst(1) ==>2,[1,2],3,[3],4,[1,2,3]<== main <<< strLst(2) ==>1,[],2,[],3,[1,2,3],1,[],2,[],3,[]<== main <<< strLst(3) ==>1,[1,2,3],2,[1,2,3],3,[1,2,3]<== <<< l: 0 line ==>1,[2,3,4]<== <<< l: 1 line ==>2,[1,2],3,[3],4,[1,2,3]<== <<< l: 2 line ==>1,[],2,[],3,[1,2,3],1,[],2,[],3,[]<== <<< l: 3 line ==>1,[1,2,3],2,[1,2,3],3,[1,2,3]<== main <<< levelOrder root: 1 2 3 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 main <<< inOrder: 1 2 1 2 3 3 1 1 2 3 2 1 2 3 3 1 2 3 4 1 2 3 main <<< leaf nodes: 1 [], 2 [] 8 1 8,[] main <<< sum: 8 main <<< lines: 1 main <<< strLst(0) ==>8,[]<== <<< l: 0 line ==>8,[]<== main <<< levelOrder root: 8 main <<< inOrder: 8 main <<< leaf nodes: 8 []
As the development of the solution progressed, we added a function to perform an in-order traversal of the tree. The reason for it was to determine if an approach based on in-order traversal could work for our function of interest. It is not shown here but I also tried a pre-order and a post-order traversal functions. They did not pay off but once the in-order function was operational, the other two were quite simple to develop and test. Keep in mind that such functions ARE NOT PART OF THE SOLUTION.
Back to our latest set of test cases, after processing all 4 input lines and calling the function that performs a level-order traversal, followed by the in-order traversal, it seems that we call the function of interest and display the associated results. Note that we have selected the same nodes we found in our diagram.
Before we look at all the code we wrote for the test scaffold and our solution, I wish to note that one of the best approaches is to start with the basics to verify our knowledge and then build up to a solution. You can always call it the minimum viable product (MVP) and then spend additional time, if needed, to optimize it. In this case I thought things were good enough.
/**
* Test scaffold
*
* !!! NOT PART OF THE SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read sum ****
int sum = Integer.parseInt(br.readLine().trim());
// **** read the number of input lines ****
int lines = Integer.parseInt(br.readLine().trim());
// **** read the data to build a general tree ****
List<String> strLst = new ArrayList<String>();
for (int i = 0; i < lines; i++)
strLst.add(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< sum: " + sum);
System.out.println("main <<< lines: " + lines);
for (int i = 0; i < strLst.size(); i++)
System.out.println("main <<< strLst(" + i + ") ==>" + strLst.get(i) + "<==");
// **** populate the tree ****
GTNode root = populate(strLst);
// **** display the tree (level order traversal) ****
System.out.println("main <<< levelOrder root: ");
levelOrder(root);
// **** in-order tree traversal ****
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println("");
// // **** post-order tree traversal ****
// System.out.print("main <<< postOrder: ");
// postOrder(root);
// System.out.println("");
// **** call function of interest and display result ****
System.out.println("main <<< leaf nodes: " + sumNodes(root, sum));
}
We use a buffered reader to read the input values and populate the initial variables. I missed to say that in the second and last set of test cases, the first line holds the target value for the sum. The other input lines remain the same.
Once we have the lines describing our tree, we call a function to populate the tree. Note that such function IS NOT PART OF THE SOLUTION.
We then display the values for the nodes of our tree in level-order and in-order traversals. The idea of the traversals was to verify all was well with the tree and to determine if the in-order traversal was the best way to proceed.
The last line in our test scaffold makes a call to the function of interest with the root of the tree and the target value which we named sum.
/**
* Define a basic general tree node.
*/
static class GTNode {
public int val;
public List<GTNode> children;
public GTNode(int val) { this.val = val; this.children = new ArrayList<GTNode>(); }
public GTNode(int val, List<GTNode> children) { this.val = val; this.children = children; }
@Override
public String toString() {
StringBuilder sb = new StringBuilder(this.val + " [");
for (int i = 0; i < this.children.size(); i++) {
sb.append(this.children.get(i).val);
if (i + 1 < this.children.size()) sb.append(",");
}
sb.append("]");
return sb.toString();
}
}
The initial problem did not define the class for the GTNode. I had to define the class members and two constructors. For testing and to display the results, we also added the toString() method.
/**
* Populate the general tree.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static public GTNode populate(List<String> strLst) {
// **** sanity checks ****
if (strLst == null || strLst.size() == 0) return null;
// **** initialization *****
GTNode root = null;
List<GTNode> prev = new ArrayList<>();
// **** loop processing one tree level at a time (bottom-top) ****
for (int l = 0; l < strLst.size(); l++) {
// **** get current line to parse ****
String line = strLst.get(l);
// ???? ????
System.out.println("<<< l: " + l + " line ==>" + line + "<==");
// **** parse this line ****
List<GTNode> curr = parseLine(line);
// **** populate the root node ****
if (root == null) {
// **** populate current level removing node from curr ****
root = curr.remove(0);
// **** update prev for next loop ****
prev.add(root);
}
// **** populate this tree level ****
else {
// **** reset offset ****
int offset = 0;
// **** for each node in prev nodes ***
for (int p = 0; p < prev.size(); p++) {
// **** for ease of use ****
GTNode dst = prev.get(p);
// **** replace each children ****
List<GTNode> dstChildren = dst.children;
// **** replace each children node with nodes in curr ****
for (int c = 0; c < dstChildren.size(); c++) {
// **** for ease of use ****
GTNode src = curr.get(c + offset);
// **** replace dst with src node ****
dstChildren.remove(c);
dstChildren.add(c, src);
}
// **** update offset in curr ****
offset += dstChildren.size();
}
// **** prev becomes curr ****
prev = curr;
}
}
// **** return the root of the general tree ****
return root;
}
This function is used to create and populate a tree using an array of input lines describing it. This code IS NOT PART OF THE SOLUTION. When you solve a problem at popular websites i.e., Codility_, HackerRank and LeetCode just to mention a few, you are always provided with a set of test cases and a test scaffold so you can test your code. In our case we developed such a framework.
/**
* Parse this level of the general tree.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static public List<GTNode> parseLine(String line) {
// **** sanity checks ****
if (line == null || line.length() == 0) return null;
// **** initialization ****
List<GTNode> nodeList = new ArrayList<>();
List<GTNode> children = null;
int j = 0;
// **** traverse the line parsing nodes ****
for (int i = 0; i < line.length(); ) {
// **** extract node value ****
j = line.indexOf(',', i);
int nodeVal = Integer.parseInt(line.substring(i, j));
// **** look for `[` ****
i = line.indexOf('[', i);
// **** look for `]` ****
j = line.indexOf("]", i);
// **** extract string with the node list ****
String nodeChildren = line.substring(i + 1, j);
// **** update i for the next pass ****
i = j + 2;
// **** generate list of children ****
if (!nodeChildren.isBlank()) {
// **** list of child node values ****
List<Integer> vals = Stream.of(nodeChildren.split(","))
.map(String::trim)
.map(Integer::parseInt)
.collect(Collectors.toList());
// **** build list of children ****
children = new ArrayList<>();
for (int v : vals)
children.add(new GTNode(v));
} else
children = new ArrayList<>();
// **** create and populate node ****
GTNode node = new GTNode(nodeVal, children);
// **** append node to list ****
nodeList.add(node);
}
// **** return list of nodes associated with the specified line ****
return nodeList;
}
This function is used to parse a single input line. The result is a list of nodes of type GTNode which will be used to update the tree under construction.
/**
* Level order tree traversal.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static public void levelOrder(GTNode root) {
// **** ****
if (root == null) return;
// **** create queue ****
Queue<GTNode> q = new LinkedList<>();
// **** prime queue ****
q.add(root);
// **** process all the nodes in the tree ****
while (!q.isEmpty()) {
// **** number of children ****
int n = q.size();
// **** loop once per child ****
while (n > 0) {
// **** remove next item from the queue ****
// GTNode p = q.peek();
// q.remove();
GTNode p = q.remove();
// **** print this node ****
System.out.print(p.val + " ");
// **** enqueue all children of p ****
for (int i = 0; i < p.children.size(); i++)
q.add(p.children.get(i));
// **** decrement node count ****
n--;
}
// **** new line between levels ****
System.out.println();
}
}
This function is used to visualize the tree we have defined and created in order to verify that all is well with the tree.
/**
* In-order tree traversal.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static public void inOrder(GTNode root) {
// **** end condition ****
if (root == null) return;
// **** visit node ****
System.out.print(root.val + " ");
// **** recurse ****
for (GTNode c : root.children)
inOrder(c);
}
This function is used to implement an in-order tree traversal. By looking at the tree and knowing the requirements for the problem, we can visualize at a higher level what needs to be done by our function of interest which we have not started to develop yet!
/**
* Post-order tree traversal.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static public void postOrder(GTNode root) {
// **** end condition ****
if (root == null) return;
// **** recurse ****
for (int i = root.children.size() - 1; i >= 0; i--)
postOrder(root.children.get(i));
// **** visit node ****
System.out.print(root.val + " ");
}
This function with several variations was created to experiment with different tree traversals like we do with binary trees. A call to it in the test scaffold has been commented out. I already had an approach that was very promising using in-order traversal. I just felt like experimenting and learning.
/**
* Return string with leaf nodes whose paths from the root add up to sum.
*
* Recursion entry point.
*
* Execution: O(n) - Space: O(n)
*/
static public String sumNodes(GTNode root, int target) {
// **** sanity check(s) ****
if (root == null) return "";
if (root.children.size() == 0) {
if (root.val == target)
return root.toString();
return "";
}
// **** initialization ****
Stack<GTNode> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
int[] sum = new int[] {0};
// **** start recursion ****
sumNodes(root, target, stack, sum);
// **** build string from stack contents ****
while (!stack.isEmpty()) {
sb.append(stack.pop().toString());
if (!stack.isEmpty()) sb.append(", ");
}
// **** return string with leaf nodes whose path adds to target ****
return sb.toString();
}
This is the entry point for the recursive function of interest. We are provided with the root of the tree and a target value for the sum of nodes in a path from the root to a leaf node. The function checks all paths and leaf nodes as we will see shortly.
We start with sanity checks and initialization steps. The stack is used to keep track of the leaf nodes of interest, the string builder is used to generate the string returned by this function, and the int[] array is used to hold and update the sum of the nodes during the tree traversal operation.
/**
* Return string with leaf nodes whose paths from the root add up to sum.
* Recursive call.
*
* Execution: O(n) - Space: O(1)
*/
static public void sumNodes(GTNode root, int target, Stack<GTNode> stack, int[] sum) {
// **** end condition ****
if (root == null) return;
// **** increment sum ****
sum[0] += root.val;
// **** recurse ****
for (GTNode c : root.children)
sumNodes(c, target, stack, sum);
// **** check if this is a leaf noded and the sum is equal to the target value ****
if (root.children.size() == 0 && sum[0] == target)
stack.push(root);
// **** decrement sum ****
sum[0] -= root.val;
}
This recursive function is called by the previous entry point.
As arguments we have the root of the tree, the target value for the sum which we should check when we are in a leaf node, the stack used to save the leaf nodes as we find them, and an array holding the current sum. We need to use an array to update the sum since basic data types are passed by value.
We start by checking for the end condition. As we will see, there is no need because we only call this function with non-null values.
We then increment the value of the sum to include the current node.
We then recursively call this function for all the children in this node.
After we return from the recursive call, we check if this is a leaf node and the sum matches the target value. If so, we push the node into the stack.
Finally, we decrement the sum for the next recursive call.
In conclusion, we created an entry point for recursion and then called the recursive function. Those two functions implement the entire solution for this problem.
I did a quick search on my blog to see if I could find the same requirements using a binary tree. I did not. Perhaps I will implement such a solution given that I already have a framework to build binary trees.
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., Codility_, HackerRank, LeetCode). This problem did not come from such sites. That said, if you run into a similar problem online, please leave me a note in the comments section of this post.
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