-
Notifications
You must be signed in to change notification settings - Fork 0
/
Ceil from BST
34 lines (32 loc) · 1.57 KB
/
Ceil from BST
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
27
28
29
30
31
32
33
34
// problem url: https://www.codingninjas.com/codestudio/problems/920464?topList=striver-sde-sheet-problems&utm_source=striver&utm_medium=website&leftPanelTab=0
// mode: Easy
// Ceil from BST
//################################################################## Recursive ##########################################################################################
void findCeil(BinaryTreeNode<int> *node, int &x, int &minValGreaterThanX){
if(node==nullptr) return;
if(node->data >= x)
minValGreaterThanX = min(minValGreaterThanX, node->data);
if(node->data > x) findCeil(node->left, x, minValGreaterThanX);
findCeil(node->right, x, minValGreaterThanX);
}
int findCeil(BinaryTreeNode<int> *node, int x){
int minValGreaterThanX = INT_MAX;
findCeil(node, x, minValGreaterThanX);
return minValGreaterThanX==INT_MAX ? -1 : minValGreaterThanX;
}
//################################################################## Iterative ###########################################################################################
#include <bits/stdc++.h>
int findCeil(BinaryTreeNode<int> *node, int x){
int minValGreaterThanX = INT_MAX;
stack<BinaryTreeNode<int>*> st;
if(node) st.push(node);
while(!st.empty()){
BinaryTreeNode<int> *node = st.top();
st.pop();
if(node->data >= x)
minValGreaterThanX = min(minValGreaterThanX, node->data);
if(node->left && node->data > x) st.push(node->left);
if(node->right) st.push(node->right);
}
return minValGreaterThanX==INT_MAX ? -1 : minValGreaterThanX;
}