Note: All solutions are in Java
Approach 1: Traverse whole tree
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null) return 0; // base case.
return (L <= root.val && root.val <= R ? root.val : 0) + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R);
}
This is an acceptable solution but it doesn’t leverage the properties of a BST so it will perform worse than the solutions mentioned below.
Approach 2: Traverse only potential nodes
This method leverages the property of a BST that the left subtree contains nodes less than that node and the right subtree contains node greater than that node. So if we come across a node whole value is less that or equal to L, we do not need to traverse its left subtree. Similarly, if the value is greater than or equal to R, we do not need to traverse its right subtree.
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null) return 0; // base case.
if (root.val < L) return rangeSumBST(root.right, L, R); // left branch excluded.
if (root.val > R) return rangeSumBST(root.left, L, R); // right branch excluded.
return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R); // count in both children.
}
Approach 3: Iterative solution
public int rangeSumBST(TreeNode root, int L, int R) {
Stack<TreeNode> stk = new Stack<>();
stk.push(root);
int sum = 0;
while (!stk.isEmpty()) {
TreeNode n = stk.pop();
if (n == null) { continue; }
if (n.val > L) { stk.push(n.left); } // left child is a possible candidate.
if (n.val < R) { stk.push(n.right); } // right child is a possible candidate.
if (L <= n.val && n.val <= R) { sum += n.val; }
}
return sum;
}