In this post we will solve the LeetCode 1302. Deepest Leaves Sum problem using the Java programming language with the VSCode IDE on a Windows computer.
Given the root of a binary tree, return the sum of values of its deepest leaves. Constraints: o The number of nodes in the tree is in the range [1, 10^4]. o 1 <= Node.val <= 100 Related Topics: o Tree o Depth-First Search o Breadth-First Search o Binary Tree
We are given a binary tree and we need to return the sum of the values of all deepest leaves.
This implies that the nodes of interest in the tree must be in the largest possible depth.
/**
* 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 deepestLeavesSum(TreeNode root) {
}
}
The signature for the function of interest is quite simple. The root of the binary tree is passed as the only argument and the function needs to return the sum of the nodes as an integer.
Since I will be developing the code on a local computer I will not be using the online IDE provided by LeetCode. When done I will just copy and paste my code to the online IDE and submit it for evaluation. Unless you have a specific reason not to develop the solution online, I would recommend using the LeetCode online IDE.
1,2,3,4,5,null,6,7,null,null,null,null,8 main <<< strArr: [1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8] main <<< arr: [1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8] main <<< inOrder: 7 4 2 5 1 3 6 8 main <<< maxDepth: 4 main <<< sumLeafNodes: 20 <<< sum: 7 d: 4 <<< sum: 8 d: 4 main <<< deepestLeavesSum0: 15 <<< root: 1 d: 1 maxDepth: 0 <<< d: 1 maxDepth: 1 sum: 1 <<< root: 2 d: 2 maxDepth: 1 <<< d: 2 maxDepth: 2 sum: 2 <<< root: 4 d: 3 maxDepth: 2 <<< d: 3 maxDepth: 3 sum: 4 <<< root: 7 d: 4 maxDepth: 3 <<< d: 4 maxDepth: 4 sum: 7 <<< root: 5 d: 3 maxDepth: 4 <<< d: 3 maxDepth: 4 sum: 7 <<< root: 3 d: 2 maxDepth: 4 <<< d: 2 maxDepth: 4 sum: 7 <<< root: 6 d: 3 maxDepth: 4 <<< d: 3 maxDepth: 4 sum: 7 <<< root: 8 d: 4 maxDepth: 4 <<< d: 4 maxDepth: 4 sum: 15 main <<< deepestLeavesSum: 15 6,7,8,2,7,1,3,9,null,1,4,null,null,null,5 main <<< strArr: [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5] main <<< arr: [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5] main <<< inOrder: 9 2 7 1 7 4 6 1 8 3 5 main <<< maxDepth: 4 main <<< sumLeafNodes: 20 <<< sum: 9 d: 4 <<< sum: 1 d: 4 <<< sum: 4 d: 4 <<< sum: 5 d: 4 main <<< deepestLeavesSum0: 19 <<< root: 6 d: 1 maxDepth: 0 <<< d: 1 maxDepth: 1 sum: 6 <<< root: 7 d: 2 maxDepth: 1 <<< d: 2 maxDepth: 2 sum: 7 <<< root: 2 d: 3 maxDepth: 2 <<< d: 3 maxDepth: 3 sum: 2 <<< root: 9 d: 4 maxDepth: 3 <<< d: 4 maxDepth: 4 sum: 9 <<< root: 7 d: 3 maxDepth: 4 <<< d: 3 maxDepth: 4 sum: 9 <<< root: 1 d: 4 maxDepth: 4 <<< d: 4 maxDepth: 4 sum: 10 <<< root: 4 d: 4 maxDepth: 4 <<< d: 4 maxDepth: 4 sum: 14 <<< root: 8 d: 2 maxDepth: 4 <<< d: 2 maxDepth: 4 sum: 14 <<< root: 1 d: 3 maxDepth: 4 <<< d: 3 maxDepth: 4 sum: 14 <<< root: 3 d: 3 maxDepth: 4 <<< d: 3 maxDepth: 4 sum: 14 <<< root: 5 d: 4 maxDepth: 4 <<< d: 4 maxDepth: 4 sum: 19 main <<< deepestLeavesSum: 19
There are two test cases which match the ones provided by LeetCode. The test cases are separated by two blank lines.
The first line is the input for the values that will be used by my test code to generate the binary tree.
The test scaffold appeared to read the input line and put the node values into the string[] named `strArr`. The values are then converted to binary and written to the Integer[] `arr`.
The test scaffold seems to create and populate the binary tree using the values of the Integer[] `arr`.
To verify all is well the test code generates an inorder traversal of the tree. Using the diagram provided by LeetCode you can verify that the values match the structure of the specified binary tree.
It seems that the test scaffold determines the depth of the binary tree. It then computes the sum of the leaf nodes. Please note the value.
It then calls the first implementation of the function of interest. The function of interest displays a few messages to help us verify that the selected approach is working well.
When done the result is displayed. Note that the value is different from the sum of the leaf nodes. In the requirements we can only use the leaf nodes on the highest level (or depth) in the binary tree. If you look at the diagram provided by LeetCode you should be able to see which node was not included.
Our test scaffold makes a call to the second implementation of the function of interest.
Some values are displayed to help us follow the approach we have selected.
When all is set and done the result returned by the second implementation is displayed.
/**
* Test scaffold.
* !!!! NOT PART OF THE SOLUTION !!!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and populate string[] for binary tree ****
String[] strArr = br.readLine().trim().split(",");
// ***** close the buffered reader ****
br.close();
// ????? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** generate Integer[] to create and populate binary tree ****
int len = strArr.length;
Integer[] arr = new Integer[len];
for (int i = 0; i < len; i++)
arr[i] = strArr[i].equals("null") ? null : Integer.parseInt(strArr[i]);
// ????? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate per level the binary tree ****
BST bt = new BST();
bt.root = bt.populate(arr);
// ???? traverse binary tree ????
System.out.println("main <<< inOrder: " + bt.inOrder(bt.root));
// ???? determine maximum depth of the binary tree ????
System.out.println("main <<< maxDepth: " + bt.maxDepth(bt.root));
// ???? sum of all leave nodes (not looking for this) ????
System.out.println("main <<< sumLeafNodes: " + sumLeafNodes(bt.root));
// **** call function of interest and display result ****
System.out.println("main <<< deepestLeavesSum0: " + deepestLeavesSum0(bt.root));
// **** call function of interest and display result ****
System.out.println("main <<< deepestLeavesSum: " + deepestLeavesSum(bt.root));
}
The test scaffold matches closely the description of the test cases. Please note that the test code IS NOT PART OF THE SOLUTION.
The method used to populate the binary tree is located in the bst.java file in my GitHub repository. Please note that such code IS NOT PART OF THE SOLUTION.
/**
* Enhanced TreeNode class typically used
* to solve LeetCode binary tree problems.
*/
public class TreeNode {
// **** class members ****
int val;
int height;
TreeNode left;
TreeNode right;
/**
* Constructor.
*/
public TreeNode() {
}
/**
* Constructor.
*/
public TreeNode(int val) {
this.val = val;
this.height = 1;
}
/**
* Constructor.
*/
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
/**
* Return a string representation of this node.
*/
@Override
public String toString() {
return "(" + val + ")";
}
}
Since I did not use the online IDE provided by LeetCode I had to implement the TreeNode class. Such implementation IS NOT PART OF THE SOLUTION.
/**
* Given the root of a binary tree,
* return the sum of values of its deepest leaves.
*
* Execution: O(n) - Space: (1)
*
* Runtime: 5 ms, faster than 55.24% of Java online submissions.
* Memory Usage: 51.6 MB, less than 25.11% of Java online submissions.
*
* 35 / 35 test cases passed.
* Status: Accepted
* Runtime: 5 ms
* Memory Usage: 51.6 MB
*/
static public int deepestLeavesSum0(TreeNode root) {
// **** initialization *****
int[] d = new int[1];
// **** start recursion - O(n) ****
return deepestLeavesSum(root, maxDepth(root), d);
}
This is the first implementation of the function of interest.
We start by initializing the int[] arr `d` which will be used to track the depth of the binary tree as we traverse it.
We then start recursion by passing the root of the binary tree, a function that returns the depth of the binary tree, and the `d` int[] used to track the depth (or level) of the tree as we visit the different nodes.
/**
* Determine the maximum depth of a binary tree.
* Recursive call.
*/
static public int maxDepth(TreeNode root) {
// **** base case ****
if (root == null) return 0;
// **** initialization ****
int depth = 0;
// **** visit left node ****
depth = Math.max(depth, maxDepth(root.left) + 1);
// **** visit right node ****
return Math.max(depth, maxDepth(root.right) + 1);
}
This is the function that returns the depth of a binary tree.
As we should be able to tell, we are first traversing the tree to generate the maximum depth and then traverse it a second time to select the nodes of interest.
/**
* Auxiliary function.
* Recursive function.
* Inorder traversal.
*/
static private int deepestLeavesSum(TreeNode root, int md, int[] d) {
// **** base condition ****
if (root == null) return 0;
// **** increment depth ****
d[0]++;
// **** traverse left subtree ****
int sum = deepestLeavesSum(root.left, md, d);
// **** visiting deepest leaf node ****
if (root.left == null && root.right == null && d[0] == md) {
// **** increment sum ****
sum += root.val;
// ???? ????
System.out.println("<<< sum: " + sum + " d: " + d[0]);
}
// **** traverse right subtree ****
sum += deepestLeavesSum(root.right, md, d);
// **** decrement depth ****
d[0]--;
// **** return sum ****
return sum;
}
This is the recursive function used to traverse the binary tree computing the sum of the leaf nodes.
We start with the base case.
Note that every time the recursive function is called we need to increment the value of the depth. Towards the end of the function we need to reduce the depth that we incremented when the function was called.
We traverse the left subtree, visit the root node and then traverse the left subtree.
When we visit the root node we check if it is a deep leaf node. If so we update the `sum` variable.
When all is said and done the `sum` is returned.
Please take a look at the comments section of the entry function for this implementation. Since we computed the depth and then the sum of serial calls, we should be able to do somewhat better if we compute the `maxDepth` and the `sum` simultaneously.
/**
* Given the root of a binary tree,
* return the sum of values of its deepest leaves.
*
* Execution: O(n) - Space: (1)
*
* Runtime: 2 ms, faster than 82.96% of Java online submissions.
* Memory Usage: 51.8 MB, less than 24.81% of Java online submissions.
*
* 35 / 35 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 51.8 MB
*/
static public int deepestLeavesSum(TreeNode root) {
// **** initialization ****
int[] md = new int[1];
int[] sum = new int[1];
// **** start recursion - O(n) ****
deepestLeavesSum(root, 1, md, sum);
// **** return sum ****
return sum[0];
}
This is the second implementation of the function of interest.
We start by initializing the `md` and `sum` variables (actually they both are int[] arrays with a single element each).
We start recursion using the root of the binary tree, the depth (or level) of the root node which is 1, and pass the two variables we declared as the last two arguments.
When the recursion finishes, the `sum` argument holds the sum of all the nodes of interest in teh binary tree.
/**
* Recursive call
*/
static public void deepestLeavesSum(TreeNode root, int d, int[] maxDepth, int[] sum) {
// **** base case ****
if (root == null) return;
// ???? ????
System.out.println("<<< root: " + root.val + " d: " + d + " maxDepth: " + maxDepth[0]);
// **** update max depth and sum ****
if (d > maxDepth[0]) {
maxDepth[0] = d;
// **** start sum ****
sum[0] = root.val;
} else if (d == maxDepth[0]) {
// **** add to sum ****
sum[0] += root.val;
}
// ???? ????
System.out.println("<<< d: " + d + " maxDepth: " + maxDepth[0] + " sum: " + sum[0]);
// **** traverse left subtree ****
deepestLeavesSum(root.left, d + 1, maxDepth, sum);
// **** traverse right subtree ****
deepestLeavesSum(root.right, d + 1, maxDepth, sum);
}
The recursive call starts with the base case.
We update the `masDepth` and the `sum` as needed. The two trace messages should help us follow the process. Please note that the messages ARE NOT PART OF THE SOLUTION.
Finally we recursively call the function to traverse the left and then the right subtrees.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named DeepestLeavesSum.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
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, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John