Day 21 Binary Search Tree II | Striver 180 | takeUforward
Post
Cancel

# Day 21 Binary Search Tree II | Striver 180 | takeUforward

## 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.
Trending Tags