leetcode/findCeilingFloor.cpp at master · Mayank-Parasar/leetcode · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//
// Created by Mayank Parasar on 2019-12-19.
//

/*
 * Given an integer k and a binary search tree,
 * find the floor (less than or equal to) of k, and the ceiling (larger than or equal to) of k.
 * If either does not exist, then print them as None.
 *
 *                   8
 *                /    \
 *               4      12              <<== Tree-1
 *              / \    /  \
 *             2   6  10   14
 */

#include <iostream>
#include <vector>

using namespace std;

struct node {
    int val;
    node* left;
    node* right;

    node(int val_) {
        val = val_;
        left = nullptr;
        right = nullptr;
    }
};

void print_tree(node* node_) { // in-order traversal

    if(node_ == nullptr)
        return;
    // print the in-order tree trraversal
    print_tree(node_->left);
    cout << node_->val << " ";
    print_tree(node_->right);
}

void findFloor(node* node_, int& floor, int& k) {

    if(node_ == nullptr)
        return;

    if(k > node_->val) {
        // store
        floor = node_->val;
        // go to right
        findFloor(node_->right, floor, k);
    }
    else if(k < node_->val) {
        // don't store
        // go to left
        findFloor(node_->left, floor, k);
    }
    else if(k == node_->val) {
        floor = node_->val;
        return;
    }
}


void findCeil(node* node_, int& ceil, int& k) {
    // TODO

    if(node_ == nullptr)
        return;

    if(k > node_->val) {
        // don't store
        // go to right
        findCeil(node_->right, ceil, k);
    }
    else if(k < node_->val) {
        // store the val
        ceil = node_->val;
        // go to left
        findCeil(node_->left, ceil, k);
    }
    else if(k == node_->val) {
        ceil = node_->val;
        return;
    }
}

int main() {

    node *node1 = new node(8);
    node *node2 = new node(4);
    node *node3 = new node(12);
    node *node4 = new node(2);
    node *node5 = new node(6);
    node *node6 = new node(10);
    node *node7 = new node(14);

    // connect them:
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;

    print_tree(node1);
    cout << endl;
    int floor = -1;
    int k = 15;     // this is the number that need to be searched in the BST
    findFloor(node1, floor, k);
    if(floor == -1)
        cout << "Floor of the number is: " << "None";
    else
        cout << "Floor of the number is: " << floor;

    cout << endl;

    int ceil = -1;
    findCeil(node1, ceil, k);

    if(ceil == -1)
        cout << "Ceil of the number is: " << "None";
    else
        cout << "Ceil of the number is: " << ceil;


    return 0;
}