[AlgoExpert] Subtrees Within Range

Subtrees Within Range

  • Time : O(n)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class BST {
public:
int value;
BST *left;
BST *right;

BST(int value) {
this->value = value;
this->left = nullptr;
this->right = nullptr;
}
};
bool helper(BST* t, int l, int r, int s, int e, int& res) {
if(!t) return true;
if(l > e or r < s) return false;
bool sub = s <= t->value and t->value <= e;
sub &= helper(t->left, l, t->value, s, e, res);
sub &= helper(t->right, t->value, r, s, e, res);
if(sub) res++;
return sub;
}
int subtreesWithinRange(BST *tree, vector<int> targetRange) {
int res = 0;
helper(tree, INT_MIN, INT_MAX, min(targetRange[0], targetRange[1]), max(targetRange[0], targetRange[1]), res);
return res;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/02/PS/AlgoExpert/subtrees-within-range/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.