938. Range Sum of BST
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.
Flowchart Walkthrough
Let's analyze the problem using the algorithm flowchart, which can be found here. Here's a step-by-step walkthrough to deduce the suitable search technique for LeetCode 938, Range Sum of BST:
Is it a graph?
- Yes: A Binary Search Tree (BST) can be considered as a graph composed of nodes and edges, where each node is a vertex and each parent-child relation is an edge.
Is it a tree?
- Yes: The BST is explicitly defined as a tree data structure.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The objective is to calculate a sum within a specific range in the BST, not related to properties of DAGs like topological sorting.
Is the problem related to shortest paths?
- No: We are not looking for the shortest path in BST, but for a summation of values within a specified range.
Does the problem involve connectivity?
- No: There is no need to explore connectivity or connected components, since the BST inherently provides connectivity between nodes through its tree structure.
Does the problem have small constraints?
- Yes: The BST's size can be seen as a small constraint, and we are merely traversing it rather than performing complex operations requiring algorithms like Dijkstra's or others suited for larger constraints.
DFS/backtracking?
- Yes: Depth-First Search (DFS) is particularly suitable here to recursively traverse the BST and accumulate the sum of nodes whose values fall within the given range. It efficiently follows the tree paths and backtracks when necessary.
Conclusion: The flowchart here helps in deducing that Depth-First Search (DFS) is the optimal choice for traversing the BST and summing node values that lie within the provided range in LeetCode 938.
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:
- If the current node is null (we've reached a leaf's child), we can stop traversing this path.
- 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. - 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 thanlow
. - 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 thanhigh
.
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.
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:
-
Initialization: A variable
self.ans
is initialized to0
. This will accumulate the sum of the node values that are within the range[low, high]
. -
Recursive Function (
search
): A nested functionsearch
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. -
Base Case: At the beginning of the
search
function, there is a check to see if the current node isNone
. If it is, the function returns immediately. This check acts as the base case of the recursion, terminating the traversal at leaf nodes. -
Range Check:
- If the current node's value is within the range
[low, high]
(inclusive), the value is added toself.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 bothnode.left
andnode.right
.
- If the current node's value is within the range
-
BST Property Utilization:
- If the current node's value is less than
low
, the function calls itself recursively onnode.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 onnode.left
as all right child nodes of the current node are guaranteed to be out of the range.
- If the current node's value is less than
-
Starting the Traversal: The recursive
search
function is first called on the root node to start the depth-first traversal. -
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 therangeSumBST
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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]:
15 / \ 10 20 / \ \ 5 13 25 \ 11
Now let's walk through how the solution would process this tree:
-
The
rangeSumBST
function initializesself.ans
to0
. This will hold the sum of values within the given range. -
The
search
function is called with the root node (15). Since 15 is within the range [10, 22], it is added toself.ans
(0 + 15 = 15), and thesearch
function will be called on both its left child (10) and right child (20). -
The
search
function is now called with node 10. Since 10 is also within the range, we add it toself.ans
(15 + 10 = 25), and callsearch
on both of its children (5 and 13). -
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 thanlow
(10), we do not callsearch
on its left subtree, and there is no right subtree to explore. -
The
search
function is next called with node 13, which falls within the range. Therefore, 13 is added toself.ans
(25 + 13 = 38), and since it has a right child (11) that could be within the range,search
is called on node 11. -
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. -
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 toself.ans
(49 + 20 = 69). Since there is a right child (25) and it is potentially within the range, we callsearch
on it. -
Node 25 is greater than
high
(22), so we don't add it toself.ans
. Also, since its value is greater thanhigh
, 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
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
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
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 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
Want a Structured Path to Master System Design Too? Donāt Miss This!