Sponsored
Sponsored
This approach involves performing a recursive in-order traversal to accumulate the sum of nodes within the given value range.
Because of the BST properties, the in-order traversal naturally allows visiting nodes in a sorted order, which means that once the current node value is larger than 'high', you can stop traversing further right subtree. Similarly, if the current node value is smaller than 'low', you can avoid traversing the left subtree further.
Time Complexity: O(N), where N is the number of nodes in the tree since in the worst case we must visit all nodes.
Space Complexity: O(H), where H is the height of the tree (accounting for the recursion stack).
1
2public class TreeNode {
3 public int val;
4 public TreeNode left;
5 public TreeNode right;
6 public TreeNode(int value) { val = value; }
7}
8
9public class Solution {
10 public int RangeSumBST(TreeNode root, int low, int high) {
11 if (root == null) return 0;
12 if (root.val < low)
13 return RangeSumBST(root.right, low, high);
14 if (root.val > high)
15 return RangeSumBST(root.left, low, high);
16 return root.val + RangeSumBST(root.left, low, high) + RangeSumBST(root.right, low, high);
17 }
18}
19In this C# implementation, the recursive function RangeSumBST checks node values and accumulates the sum of those nodes falling within the desired range.
This approach uses an iterative method with an explicit stack to facilitate an in-order traversal. Utilizing a stack allows avoiding the function call stack and can handle larger trees without risking stack overflow in languages with limitations on recursion depth.
As we push nodes onto the stack, we continue to the leftmost node, then process nodes and move to the right, ensuring nodes are visited in non-decreasing order. Only nodes within the range are added to the sum.
Time Complexity: O(N) where N is the number of nodes.
Space Complexity: O(H) where H is the height of the tree due to the stack usage.
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) { val = value; }
}
public class Solution {
public int RangeSumBST(TreeNode root, int low, int high) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
int sum = 0;
while (current != null || stack.Count > 0) {
while (current != null) {
stack.Push(current);
current = current.left;
}
current = stack.Pop();
if (current.val >= low && current.val <= high) {
sum += current.val;
}
if (current.val > high) break;
current = current.right;
}
return sum;
}
}
This C# code uses a stack to iteratively traverse the tree, collecting sums of node values that lie within the specified range, avoiding recursion through explicit stack use.