Deepest Leaves Sum Problem in Java
In this tutorial, we will learn about Deepest leaves sum problem in Java. Finding the total of the nodes' values at the lowest level of a binary tree is known as the "deepest leaves sum" problem.
The goal is to find the total of all leaf nodes that are at least one depth below a given root node in a tree.
Example:
Input: Root of the above tree
Output: 17
Explanation:
![Deepest Leaves Sum Problem in Java](https://static.tutorialandexample.com/java/deepest-leaves-sum-problem-in-java1.png)
Compare each node's level with maxDepth(the highest level reached up to this point) as you traverse the nodes. Update the maxDepth to reflect the current level if it is higher than the maximum level. Add the root data to the current sum if the current level and the maximum level are the same. Do nothing if the level is lower than maxDepth.
Approach 1: Using depth first search
ALGORITHM:
Step 1: First, determine the binary tree's depth. By figuring out the maximum depths of the left and right subtrees and then adding 1 to the maximum of those depths, we can accomplish this recursively.
Step 2: Retrace the tree to determine the total number of nodes at that depth after we know the tree's depth. We explore the tree recursively, tracking the current depth as we go. We figure out the total of the node values at the target depth when we get there.
Step 3: Use the two auxiliary functions: findDepth() to get the tree's depth and findSumAtDepth() to determine the total number of values at the desired depth.
To find the sum of the deepest leaves, we first construct a sample binary tree in the main method and then instantiate the solution class.
FileName: DeepestSum.java
public class DeepestSum { static int deepestSum = 0; static int maxDepth = Integer.MIN_VALUE; static class TreeNode { int data; TreeNode left; TreeNode right; }; // The ability to retrieve a new node static TreeNode createNode(int data) { TreeNode node; node = new TreeNode(); node.data = data; node.left = null; node.right = null; return node; } // The function that determines the total number of nodes present at the greatest depth. // To the current sum, add the root data. static void sumOfNodesAtMaxDepth(TreeNode root, int currentDepth) { if(root == null) return; if(currentDepth > maxDepth) { deepestSum = root.data; maxDepth = currentDepth; } else if(currentDepth == maxDepth) { deepestSum = deepestSum + root.data; } sumOfNodesAtMaxDepth(root.left, currentDepth + 1); sumOfNodesAtMaxDepth(root.right, currentDepth + 1); } public static void main(String[] args) { TreeNode root; root = createNode(1); root.left = createNode(2); root.right = createNode(3); root.left.left = createNode(4); root.left.right = createNode(5); root.right.left = createNode(6); root.right.right = createNode(7); sumOfNodesAtMaxDepth(root, 0); System.out.println(deepestSum); } }
Output:
22
Complexity Analysis:
Time Complexity: The time complexity of a program is O(n) Since we only visit each node once.
Space Complexity: The space complexity of a program is O(h). Here, h is the tree's height, and the recursive call stack makes use of the extra space.
Approach 2: Using a queue
ALGORITHM:
Step 1: Compute the total of all the nodes for every level.
Step 2: Place every node in the tree in the queue.
Step 3: Determine the total number of nodes.
FileName: DeepestLeaveSum.java
import java.util.*; public class DeepestLeaveSum { static class TreeNode { int value; TreeNode l; TreeNode r; } static TreeNode createNode(int data) { TreeNode node; node = new TreeNode(); node.value = data; node.l = null; node.r = null; return node; } // To find the sum of the deepest nodes, use an iterative function. public static int deepestLeavesSum(TreeNode root) { if (root == null) { return 0; } Queuequeue = new LinkedList<>(); queue.offer(root); int sumOfCurrentLevel = 0; while (!queue.isEmpty()) { int size = queue.size(); sumOfCurrentLevel = 0; while (size-- > 0) { TreeNode head = queue.poll(); sumOfCurrentLevel += head.value; if (head.l != null) { queue.offer(head.l); } if (head.r != null) { queue.offer(head.r); } } } return sumOfCurrentLevel; } public static void main(String[] args) { TreeNode root; root = createNode(1); root.l = createNode(2); root.r = createNode(3); root.l.l = createNode(4); root.l.r = createNode(5); root.r.l = createNode(6); root.r.r = createNode(7); System.out.println(deepestLeavesSum(root)); } }
Output:
22
Complexity Analysis:
Time Complexity: The time complexity of a program is O(N) Since we only visit each node once.
Space Complexity: The space complexity of a program is O(b). Here, h is the tree's height, and the recursive call stack makes use of the extra space.