Home Binary Search Tree II | Striver’s SDE Sheet
Post
Cancel

Binary Search Tree II | Striver’s SDE Sheet

Problem 1: Floor in a BST

You are given a BST (Binary search tree) with’ N’ number of nodes and a value ‘X’. Your task is to find the greatest value node of the BST which is smaller than or equal to ‘X’.

Worst

Transerse the whole tree. Keep track of the closest smaller or same element.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(n) $

Better

Check whether the key is < or == or > than the root node.

Time Complexity: $ O(h) $

Auxiliary Space: $ O(n) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int floorInBST(TreeNode<int> * root, int X)
{
    if (!root)
        return INT_MAX;
 
    if (root->val == X)
        return root->val;
 
    if (root->val > X)
        return floorInBST(root->left, X);
 
    int ans = floorInBST(root->right, X);
    return ans <= X ? ans : root->val;
}

Optimal

Check whether the key is < or == or > than the root node.

Time Complexity: $ O(h) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int floorInBST(TreeNode<int> * root, int X)
{
    if (!root)
        return INT_MAX;
 
    if (root->val == X)
        return root->val;
 
    if (root->val > X)
        return floorInBST(root->left, X);
 
    int ans = floorInBST(root->right, X);
    return ans <= X ? ans : root->val;
}

Problem 2: Ceil in a BST

Ninja is given a binary search tree and an integer. Now he is given a particular key in the tree and returns its ceil value. Can you help Ninja solve the problem ?

Worst

Transerse the whole tree. Keep track of the least greater than or same element.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(n) $

Better

Check whether the key is < or == or > than the root node.

Time Complexity: $ O(h) $

Auxiliary Space: $ O(n) $

1
2
3
4
5
6
7
8
9
10
11
12
int findCeil(BinaryTreeNode<int> *root, int x){
   
    int ans = -1;
    if (!root) return ans;
    
    if (root -> data == x) return root -> data;
    
    if (root -> data < x) return findCeil(root->right, x);
 
    ans = findCeil(root->left, x);
    return ans >= x ? ans : root->data;
}

Optimal

Check whether the key is < or == or > than the root node.

Time Complexity: $ O(h) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
int findCeil(BinaryTreeNode<int> *root, int x){
   
    int ans = -1;
    if (!root) return ans;
    
    if (root -> data == x) return root -> data;
    
    if (root -> data < x) return findCeil(root->right, x);
 
    ans = findCeil(root->left, x);
    return ans >= x ? ans : root->data;
}
This post is licensed under CC BY 4.0 by the author.

Binary Search Tree I | Striver’s SDE Sheet

Binary Tree IV | Striver’s SDE Sheet