Range SUM of BST

Given the root node of a binary search tree, return the sum of values of all nodes with a value between L and R (inclusive). The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:

  1. The number of nodes in the tree is at most 10000.
  2. The final answer is guaranteed to be less than 2^31.
/**
 * 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;
 *     }
 * }
 */

Recursive Solution:

int sum = 0;
public int rangeSumBST(TreeNode root, int L, int R) {
	if(root == null){
		return 0;
	}
	if(root.val >= L && root.val <= R){
		sum += root.val;
	}
	rangeSumBST(root.left, L, R);
	rangeSumBST(root.right, L, R);
	return sum;
}

Iterative Solution:

public int rangeSumBST(TreeNode root, int L, int R) {
	if(root == null){
		return 0;
	}
	Queue<TreeNode> queue = new LinkedList<>();
	queue.offer(root);
	int sum = 0;
	while(!queue.isEmpty()){
		TreeNode node = queue.poll();
		if(node.val <= R && node.val >= L){
			sum += node.val;
		}
		if(node.left != null) queue.offer(node.left);
		if(node.right != null) queue.offer(node.right);
	}
	return sum;
}

Categories: Binary Tree

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s