700547. Sum of leaf nodes in BST
Here is a detailed Markdown blog post for the problem "Sum of leaf nodes in BST":
Sum of leaf nodes in BST
Summary
Given a Binary Search Tree (BST), find the sum of all leaf nodes. A leaf node is an internal node that has no children.
Detailed Explanation
To solve this problem, we can start by recursively traversing the tree and keeping track of whether each node is a leaf or not. We'll use an in-order traversal to ensure that we visit the left subtree before the current node, then the right subtree. This way, we'll encounter all leaf nodes first.
Here's the step-by-step breakdown:
- Start at the root of the tree.
- If the current node is a leaf (i.e., it has no children), add its value to our sum.
- Recursively traverse the left subtree (if it exists).
- Recursively traverse the right subtree (if it exists).
Here's an ASCII art diagram to help illustrate this:
5
/ \
2 8
/ \ / \
1 3 6 9
In this example, the leaf nodes are 1, 3, and 9. Our algorithm would visit these nodes first and add their values to our sum.
The time complexity of this algorithm is O(n), where n is the number of nodes in the tree, because we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.
Optimized Solutions
Java
class Node {
int val;
Node left, right;
Node(int v) {
val = v;
left = right = null;
}
}
public class Main {
public static int sumLeafNodes(Node root) {
if (root == null) return 0;
int sum = 0;
if (root.left == null && root.right == null) {
sum += root.val;
} else {
sum += sumLeafNodes(root.left);
sum += sumLeafNodes(root.right);
}
return sum;
}
public static void main(String[] args) {
Node root = new Node(5);
root.left = new Node(2);
root.right = new Node(8);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(6);
root.right.right = new Node(9);
System.out.println(sumLeafNodes(root)); // Output: 13
}
}