# How is the space complexity O(LogN) for rangeSumBST problem

Recursive

class Solution {

int ans;
public int rangeSumBST(TreeNode root, int L, int R) {
ans = 0;
dfs(root, L, R);
return ans;
}

public void dfs(TreeNode node, int L, int R) {
if (node != null) {
if (L <= node.val && node.val <= R)
ans += node.val;
if (L < node.val)
dfs(node.left, L, R);
if (node.val < R)
dfs(node.right, L, R);
}
}
}


Iterative

class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
int ans = 0;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (L <= node.val && node.val <= R)
ans += node.val;
if (L < node.val)
stack.push(node.left);
if (node.val < R)
stack.push(node.right);
}
}
return ans;
}
}


Suppose L is Integer.MIN_VALUE and R is Integer.MAX_VALUE, then wouldn't it traverse through all the nodes. Since we need to check the worst case, shouldn't it be O(N) instead of O(logN)

The space complexity is the amount of space used, which is essentially the size of your call stack in your deepest line of recursion. The runtime is indeed $$O(N)$$ but the space complexity is $$O(H)$$ where H is the height of the tree.
Even following the link you provided, they state this: 