938. Range Sum of BST

EasyTreeDepth-First SearchBinary Search TreeBinary Tree
Leetcode Link

Problem Description

The problem provides us with the root node of a binary search tree (BST) and two integer values, low and high. It asks us to calculate the sum of all the node values in the BST that fall within the inclusive range [low, high]. This means that if a node's value is equal to or greater than low and equal to or less than high, it should be included in our sum. The binary search property of the tree, where left child nodes are less than the parent node and right child nodes are greater, can be used to optimize our search for the range.

Intuition

The intuition behind the solution approach is to perform a depth-first traversal of the BST while leveraging the BST property to avoid unnecessary traversal. The steps of the approach are:

  1. If the current node is null (we've reached a leaf's child), we can stop traversing this path.
  2. If the current node's value falls within [low, high], we add it to the sum and continue to search both the left and right subtrees as there may be more nodes within the range.
  3. If the current node's value is less than low, we only need to traverse the right subtree because all values in the left subtree will also be less than low.
  4. If the current node's value is greater than high, we only need to traverse the left subtree, as all values in the right subtree will be greater than high.

Using these rules, the search efficiently skips parts of the tree that don't contribute to the range sum, which optimizes our algorithm significantly compared to a naive approach that checks every node.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution involves the use of a recursive helper function called search, nested within the main function rangeSumBST. This is a common design pattern in recursive solutions, allowing the use of helper functions with additional parameters without changing the main function's signature. The algorithm uses this recursive function to perform a modified in-order traversal of the binary search tree. Here's a breakdown of how the algorithm works, with references to the data structures and patterns used:

  1. Initialization: A variable self.ans is initialized to 0. This will accumulate the sum of the node values that are within the range [low, high].

  2. Recursive Function (search): A nested function search is defined, which takes the current node as its parameter. The use of recursion is key here, enabling the function to traverse the tree depth-first.

  3. Base Case: At the beginning of the search function, there is a check to see if the current node is None. If it is, the function returns immediately. This check acts as the base case of the recursion, terminating the traversal at leaf nodes.

  4. Range Check:

    • If the current node's value is within the range [low, high] (inclusive), the value is added to self.ans. As this node is within the range, there might be other nodes within the range both to the left and right, so the function recursively calls itself on both node.left and node.right.

  5. BST Property Utilization:

    • If the current node's value is less than low, the function calls itself recursively on node.right as all left child nodes of the current node are guaranteed to be out of the range.
    • If the current node's value is greater than high, the function calls itself recursively on node.left as all right child nodes of the current node are guaranteed to be out of the range.

  6. Starting the Traversal: The recursive search function is first called on the root node to start the depth-first traversal.

  7. Returning the Answer: Finally, after the recursive calls have completed, self.ans contains the sum of the values within the range, and this value is returned by the rangeSumBST function.

The use of a BST's intrinsic properties allows the algorithm to avoid inspecting every single node in the tree, thereby significantly improving efficiency, especially in cases where the range bounds are far from the minimum and maximum values in the tree. The space complexity is proportional to the height of the tree (O(H)) due to the recursion stack, and the time complexity is O(N) in the worst case when the tree is unbalanced, but it could be much less if the tree is balanced and the search prunes branches effectively.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the following binary search tree (BST) and the range [low, high] = [10, 22]:

1          15
2         /  \
3       10    20
4      /  \    \
5     5   13    25
6       \
7       11

Now let's walk through how the solution would process this tree:

  1. The rangeSumBST function initializes self.ans to 0. This will hold the sum of values within the given range.

  2. The search function is called with the root node (15). Since 15 is within the range [10, 22], it is added to self.ans (0 + 15 = 15), and the search function will be called on both its left child (10) and right child (20).

  3. The search function is now called with node 10. Since 10 is also within the range, we add it to self.ans (15 + 10 = 25), and call search on both of its children (5 and 13).

  4. When called with node 5, the function does not add its value to self.ans since 5 is outside the range. As 5 is less than low (10), we do not call search on its left subtree, and there is no right subtree to explore.

  5. The search function is next called with node 13, which falls within the range. Therefore, 13 is added to self.ans (25 + 13 = 38), and since it has a right child (11) that could be within the range, search is called on node 11.

  6. Node 11 is within the range, so its value is added to self.ans (38 + 11 = 49). Node 11 has no children, so no further calls are made here.

  7. Back to the root, the search function is called with the node 20. This node's value is within the range and therefore is sum-up to self.ans (49 + 20 = 69). Since there is a right child (25) and it is potentially within the range, we call search on it.

  8. Node 25 is greater than high (22), so we don't add it to self.ans. Also, since its value is greater than high, we do not explore its right subtree (not existing in this case), and because it has no left child, the traversal of this path ends.

With all paths explored, the final sum calculated is self.ans = 69, and the rangeSumBST returns this sum as the answer.

This example demonstrates how the algorithm effectively uses the BST properties to skip over irrelevant parts of the tree (for instance, not exploring left subtrees of nodes with values less than low, and right subtrees of nodes with values greater than high), thus optimizing the search for efficiency.

Solution Implementation

1# Definition for a binary tree node
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
10        # Helper function to perform DFS and accumulate node values within the range [low, high]
11        def dfs(node):
12            # If the current node is None, return and do nothing
13            if not node:
14                return
15          
16            # If the current node's value is within the range [low, high], add it to the total sum
17            if low <= node.val <= high:
18                self.total_sum += node.val
19                # Continue searching to the left and right as there may still be values
20                # within the range [low, high]
21                dfs(node.left)
22                dfs(node.right)
23            elif node.val < low:
24                # If the current node's value is less than the low value of the range
25                # then only search to the right as all left values will also be less
26                dfs(node.right)
27            elif node.val > high:
28                # If the current node's value is greater than the high value of the range
29                # then only search to the left as all right values will also be greater
30                dfs(node.left)
31
32        # Initialize the total_sum as 0 before starting the DFS
33        self.total_sum = 0
34        # Start the depth-first search from the root node
35        dfs(root)
36        # After DFS, return the total sum of values within [low, high]
37        return self.total_sum
38
1// Class containing the solution method to calculate the sum of values of all nodes within a range of a BST
2class Solution {
3    // This method computes the sum of values falling within the [low, high] range in a BST
4    public int rangeSumBST(TreeNode root, int low, int high) {
5        // If the current node is null, return 0 since there are no values to add
6        if (root == null) {
7            return 0;
8        }
9      
10        // If the value of the current node is within the [low, high] range,
11        // include its value in the sum, and continue searching in both left and right subtrees
12        if (low <= root.val && root.val <= high) {
13            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
14        } 
15        // If the value of the current node is less than the lower bound,
16        // skip the left subtree because all values there will be out of range,
17        // and only continue searching in the right subtree
18        else if (root.val < low) {
19            return rangeSumBST(root.right, low, high);
20        } 
21        // If the value of the current node is greater than the upper bound,
22        // skip the right subtree because all values there will be out of range,
23        // and only continue searching in the left subtree
24        else {
25            return rangeSumBST(root.left, low, high);
26        }
27    }
28}
29
30// Definition for a binary tree node.
31class TreeNode {
32    int val;         // The integer value of the node
33    TreeNode left;   // Reference to the left child
34    TreeNode right;  // Reference to the right child
35
36    // Constructor for creating a new node without children
37    TreeNode() {}
38
39    // Constructor for creating a new node with a given value
40    TreeNode(int val) {
41        this.val = val;
42    }
43
44    // Constructor for creating a new node with a given value and references to left and right children
45    TreeNode(int val, TreeNode left, TreeNode right) {
46        this.val = val;
47        this.left = left;
48        this.right = right;
49    }
50}
51
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    /**
15     * Computes the sum of values of all nodes with a value in the range [low, high].
16     * Utilizes the BST property to prune branches that cannot contain values in the range.
17     *
18     * @param root Pointer to the root of the binary search tree (BST).
19     * @param low The lower bound of the range (inclusive).
20     * @param high The upper bound of the range (inclusive).
21     * @return The sum of values in the specified range.
22     */
23    int rangeSumBST(TreeNode* root, int low, int high) {
24        if (root == nullptr) {
25            // Base case: if the current node is null, return sum of 0
26            return 0;
27        }
28
29        // Check if the current node's value is within the range [low, high]
30        if (low <= root->val && root->val <= high) {
31            // If it is in the range, include the node's value in the sum,
32            // and continue to check both left and right children
33            return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
34        } else if (root->val < low) {
35            // If current node's value is less than low, no need to check
36            // the left subtree as all values will be out of range; proceed
37            // to check the right child
38            return rangeSumBST(root->right, low, high);
39        } else {
40            // If current node's value is greater than high, no need to check
41            // the right subtree as all values will be out of range; proceed
42            // to check the left child
43            return rangeSumBST(root->left, low, high);
44        }
45    }
46};
47
1// Typescript representation of a binary search tree node
2type TreeNode = {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6};
7
8/**
9 * Computes the sum of values of all nodes with a value in the range [low, high].
10 * Utilizes the Binary Search Tree (BST) property to prune branches that cannot contain values in the range.
11 *
12 * @param root The root of the binary search tree (BST).
13 * @param low The lower bound of the range (inclusive).
14 * @param high The upper bound of the range (inclusive).
15 * @returns The sum of values within the specified range.
16 */
17function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
18  if (!root) {
19    // Base case: if the current node is null, return a sum of 0.
20    return 0;
21  }
22
23  // Check if the current node's value is within the range [low, high].
24  if (root.val >= low && root.val <= high) {
25    // The node's value falls within the range, so add it to the sum,
26    // and continue to check both the left and right subtrees.
27    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
28  } else if (root.val < low) {
29    // The current node's value is less than the low end of the range,
30    // so there is no need to check the left subtree (all values will be too small).
31    // Instead, traverse the right subtree only.
32    return rangeSumBST(root.right, low, high);
33  } else {
34    // The current node's value is greater than the high end of the range,
35    // so there is no need to check the right subtree (all values will be too large).
36    // Instead, traverse the left subtree only.
37    return rangeSumBST(root.left, low, high);
38  }
39}
40
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Time and Space Complexity

The given Python code defines a function rangeSumBST that calculates the sum of values of all nodes with a value in the range [low, high] within a binary search tree (BST). The function implements a recursive depth-first search strategy.

Time Complexity

The time complexity of the function is O(N), where N is the number of nodes in the binary search tree. This is because, in the worst-case scenario, the function may have to visit every node in the tree. However, due to the properties of a binary search tree and the pruning of branches that do not fall within the [low, high] range, the average case will likely be more efficient than this. Nonetheless, the upper bound worst-case remains O(N).

Space Complexity

The space complexity of the recursion is O(H), where H is the height of the tree. This complexity arises from the call stack that holds the recursive calls during the search process. In the worst-case scenario of a skewed binary search tree where the tree behaves like a linked list, the height of the tree could be N, making the space complexity O(N). For a balanced tree, the height of the tree would be log(N), leading to a space complexity of O(log(N)). It should be noted that this does not take into account the space used to store the binary search tree itself, only the additional space used by the recursion call stack.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Search Tree Intro

Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ