Binary Search Trees: Given a BST and a key, find the next smaller element of that key

Problem Statement:

Given a BST and a key, find the next smaller element of that key

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

key = 9

Output: 8

Solution Explanation:

Add the elements into the vector, perform binary search on the vector to arrive at the result.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};

void inorderTraversal(Tree_Node* root, vector<int>& values)
{
    if (!root)
        return;
    inorderTraversal(root->left, values);
    values.push_back(root->data);
    inorderTraversal(root->right, values);
}


int solution(Tree_Node* root, int target)
{

    vector<int> values;

    //add all the elements into the vector
    inorderTraversal(root, values);

    int left = 0;
    int right = values.size() - 1;
    int index = -1;

    while (left <= right) 
    {
        int mid = left + (right - left) / 2;

        if (values[mid] < target) {
            index = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }

    if (index == -1)
        return -1;

    return values[index];
}

int main()
{

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    Tree_Node* root = new Tree_Node(10);
    root->left = new Tree_Node(8);
    root->right = new Tree_Node(12);
    root->left->left = new Tree_Node(2);
    root->left->right = new Tree_Node(9);
    root->right->left = new Tree_Node(11);
    root->right->right = new Tree_Node(14);

    int key = 9;

    cout <<solution(root, key);

    return 0;
}

Output

8