It is a Saturday morning in what has been forecasted so far as the coldest weekend of this winter season in the Twin Cities of Minneapolis and St. Paul. I woke up this morning around 05:00 AM and the temperature was at -8F. It seems like it will go up a few degrees during the day until it starts dropping down in the mid afternoon. On Sunday we should we waking up to a balmy -20F. My wife and I did our grocery shopping for the week yesterday evening. We are not planning on leaving home this weekend.
Earlier today I read Cybersecurity: Is it Worse than We Think? authored by Chris Maurer, Kevin Kim, Dan J Kim, and Leon Allan Kappelman in the latest Communications of the ACM magazine. The article is interesting, but there was a sentence that called my attention the most. The sentence follows:
“While they [organizations] may be saying the right things in public to satisfy investors, underwriters, and customers, there is an apparent lack of urgency in promoting a truly resilient and secure organization”.
You need to read the article to fully understand the meaning. In my opinion addressing cyber threats requires an investment which has no obvious ROI. Given that the word on the street is that it is not if but when a company will be hacked, then by doing as little as possible and carrying insurance to cover the cost of a breach seems the best approach. Of course if you ask a customer whose PID has been published in the dark web, the sentiments might be quite different.
Enough chit-chat and let’s get to the main subject of this post.
Last week I was talking with a software engineer and I was asked to give a very high level approach on how to solve the following problem:
Binary Tree Max Path Sum
Find the longest path (sum), not necessarily going through the root.
Example:
1
/ \
2 4
/ \
3 6
Node {
int value;
Node* left;
Node* right;
}
Answer: 13 (4 + 1 + 2 + 6)
By looking at the example you quickly realize that the longest path is from 6->2->1->4 or vice versa, which provides the expected answer. The problem is how to solve it. The nodes of interest will be leaf nodes. It seems that we need to perform a depth first search and then maximize the distance. The complex this is how to maximize it? At the time I left it there because we just had a couple minutes available.
I went and looked up the problem in LeetCode and found problem 124 Binary Tree Maximum Path Sum a pretty good match. This is ranked as Hard in the LeetCode website so there is little chance to solve it on the fly in a couple minutes.
Well yesterday evening, after returning from grocery shopping, I had some time to give the problem a try.
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any path. Constraints: o The number of nodes in the tree is in the range [1, 3 * 104]. o -1000 <= Node.val <= 1000
The LeetCode description seems to provide additional hints as to how the problem can be approached. I had an additional idea to use the Euler tour technique and collect the node values in a data structure. I could then maximize the distance. That said; I went ahead and stayed with the depth first traversal.
One of the key points is to understand that a path is defined as any sequence of nodes from some starting node to any node in the binary tree along the parent-child connections. In addition the start and end nodes will be leaf nodes in the binary tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
}
}
The signature for the method of interest is provided. In addition we will use the TreeNode class to represent the nodes in our binary tree.
I will be solving the problem on my Windows 10 computer using the Java programming language and using the VSCode IDE. I like VSCode due to the fact that it is free and I have been using Visual Studio for decades. I currently have installed in the Windows 10 computer in which I am typing this post:
Microsoft Visual Studio Enterprise 2019 Version 16.8.5
This is among several other IDEs (i.e., Eclipse, Intellij IDEA, JetBrains, etc) that I use less frequently.
1,2,3 main <<< strArr: [1, 2, 3] main <<< arr: [1, 2, 3] main <<< bt levelOrder: 1 2,3 <<< node.val: 2 leftSum: 0 rightSum: 0 sum: 2 <<< node.val: 3 leftSum: 0 rightSum: 0 sum: 3 <<< node.val: 1 leftSum: 2 rightSum: 3 sum: 6 main <<< maxPS: 6 1,2,4,3,6 main <<< strArr: [1, 2, 4, 3, 6] main <<< arr: [1, 2, 4, 3, 6] main <<< bt levelOrder: 1 2,4 3,6 <<< node.val: 3 leftSum: 0 rightSum: 0 sum: 3 <<< node.val: 6 leftSum: 0 rightSum: 0 sum: 6 <<< node.val: 2 leftSum: 3 rightSum: 6 sum: 11 <<< node.val: 4 leftSum: 0 rightSum: 0 sum: 4 <<< node.val: 1 leftSum: 8 rightSum: 4 sum: 13 main <<< maxPS: 13 -10,9,20,null,null,15,7 main <<< strArr: [-10, 9, 20, null, null, 15, 7] main <<< arr: [-10, 9, 20, null, null, 15, 7] main <<< bt levelOrder: -10 9,20 15,7 <<< node.val: 9 leftSum: 0 rightSum: 0 sum: 9 <<< node.val: 15 leftSum: 0 rightSum: 0 sum: 15 <<< node.val: 7 leftSum: 0 rightSum: 0 sum: 7 <<< node.val: 20 leftSum: 15 rightSum: 7 sum: 42 <<< node.val: -10 leftSum: 9 rightSum: 35 sum: 34 main <<< maxPS: 42
We have three examples. The first and last were provided by LeetCode. The second is from the data shown in the example provided by the software engineer which motivated this post.
Since I am solving the problem on my machine, we need to generate some type of test scaffold which will read the input line holding the values for the nodes in Breadth First order.
It seems like our test code; which IS NOT PART OF THE SOLUTION, reads the input line, generates a String[] array and displays it. The code then populates an Integer[] array with the values converted from the String[] array. The reason is that in the last example we encounter null nodes and we have to deal with them when we attempt to populate the binary tree which will be passed as an argument to our method of interest.
Next it seems that our test code creates and populates a binary tree. The binary tree is displayed in level order.
While we are computing the result some messages are being displayed. I inserted a comment and left it uncommented so we can better visualize what is going on with the approach and code.
Finally our code seems to get back an answer from the method of interest and displays it so we can verify if the answer makes sense.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** create String[] with values for the BT ****
String[] strArr = br.readLine().trim().split(",");
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** generate an Integer[] to build the BT ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null"))
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate the binary tree ****
BST bt = new BST();
bt.root = bt.populate(arr);
// ???? ????
System.out.println("main <<< bt levelOrder:");
System.out.println(bt.levelOrder());
// **** get the maximum path sum of any path****
int maxPS = maxPathSum(bt.root);
// ???? ????
System.out.println("main <<< maxPS: " + maxPS);
}
I am not going to touch on the code for our test scaffold because we just described what it is doing. Note that we are using custom classes that we have seen in many binary tree problems in this blog. I have developed them as needed. If you do not wish to deal with the test scaffold, go the simplest route and solve the problem on-line using the IDE provided by LeetCode.
// **** holds the max path sum value ****
static int maxPS;
We will use the maxPS variable to keep track of the maximum path sum as we compute the answer for each problem.
/**
* Given the root of a binary tree, return the maximum path sum of any path.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 40.7 MB, less than 86.25% of Java online submissions.
*/
static int maxPathSum(TreeNode root) {
// **** initialization ****
maxPS = Integer.MIN_VALUE;
// **** generate the max path sum and update maxPS ****
pathSum(root);
// **** return maxPS ****
return maxPS;
}
We start by initializing the maxPS variable. This is not needed if you run a single problem, but if you are calling the method in a loop, then we need to clear the value.
We then call the method pathSum() which will update the maxPS variable. When done, our method returns the value of the maxPS variable. We have seen this setup in many recursive problems in this blog.
/**
* Depth first search based.
* Recursive method.
*/
static int pathSum(TreeNode node) {
// **** sanity check(s) ****
if (node == null)
return 0;
// **** path sum of left subtree ****
int leftSum = Math.max(0, pathSum(node.left));
// **** path sum of right subtree ****
int rightSum = Math.max(0, pathSum(node.right));
// **** compute complete path sum ****
int sum = leftSum + rightSum + node.val;
// ???? ????
System.out.println("<<< node.val: " + node.val +
" leftSum: " + leftSum + " rightSum: " + rightSum +
" sum: " + sum);
// **** update the max path sum (if needed) ****
maxPS = Math.max(maxPS, sum);
// **** return the sum of the longest path including the current node ****
return Math.max(leftSum, rightSum) + node.val;
}
Now let’s look at the “piece de resistance”. As we initially though, we will use a DFS approach. On each pass we collect the values of the left and right subtrees. We then compute the sum value of the path and update the value as needed. What is important to keep in mind, is to return the max value of the left or right subtree in addition to the value of the current node. Remember that we are traversing the tree going in an upwards direction so we only need to return the largest value of one branch.
Now that we have seen the code, go back to the test examples, and see how the output and the code explain the process in detail. It might seem easy when you see the final code, but there is a reason why this problem was tagged as Hard by LeetCode.
I liked the problem but it took me more than a couple minutes to come up with a viable solution.
Hope you enjoyed solving this problem as much as I did. 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 help out 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 e-mail message. 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 toolset.
One last thing, many thanks to all 6,548 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com