Binary Search Trees¶
A Binary Search Tree (BST) is a binary tree where each node follows the property:
- Left subtree contains values smaller than the node
- Right subtree contains values greater than the node
BSTs enable efficient search, insertion, and deletion operations.
1. Concept¶
/**Question:**
Given an array `order`, which represents the inorder traversal of a binary search tree (BST), the task is to check if it's valid or not.
**Approach:**
A binary search tree is considered valid if its inorder traversal is in non-decreasing order. We can simply iterate through the `order` array and check if each element is smaller than the next element. If we find any element that is greater than or equal to the next element, the BST is not valid, and we return `false`. Otherwise, we return `true`.
**Complexity Analysis:**
Let's analyze the time and space complexity of our approach:
- Time Complexity: O(N)
- In the worst case, we need to iterate through the entire `order` array once, where N is the number of elements in the array.
- Space Complexity: O(1)
- We are not using any additional space that grows with the input size, so the space complexity is constant.
**Code:**/
bool isValidBST(vector<int> &order) {
for (int i = 1; i < order.size(); i++) {
if (order[i - 1] >= order[i]) {
return false;
}
}
return true;
}
/**Question:**
You are given the root of a binary search tree (BST) and an integer `val`. You need to find the node in the BST whose value equals `val` and return the subtree rooted with that node. If such a node does not exist, return `NULL`.
**Approach:**
Since the given binary tree is a binary search tree, we can utilize its property to efficiently find the node with the value `val`. We start from the root and compare its value with `val`. If the current node's value is equal to `val`, we return the current node as it is the node we are looking for. If the current node's value is greater than `val`, we need to search in the left subtree because all nodes in the left subtree have smaller values. Similarly, if the current node's value is smaller than `val`, we need to search in the right subtree. We recursively perform this process until we find the desired node or reach a leaf node (where the node is not present).
**Complexity Analysis:**
Let's analyze the time and space complexity of our approach:
- Time Complexity: O(log N) on average for balanced BST, O(N) in the worst case for skewed BST.
- In a balanced binary search tree, each level reduces the search space by half, so the time complexity is logarithmic. However, in the worst case, the BST can be skewed, and we may need to traverse all nodes in one path, leading to linear time complexity.
- Space Complexity: O(H), where H is the height of the BST.
- The space complexity is determined by the recursion stack. In the average case, the height of a balanced BST is logarithmic, resulting in a logarithmic space complexity. In the worst case, when the tree is skewed, the height is N, resulting in a space complexity of O(N).
**Code:**/
TreeNode* searchBST(TreeNode* root, int val) {
if (!root) return NULL;
if (root->val == val) return root;
if (root->val > val) return searchBST(root->left, val);
else return searchBST(root->right, val);
}
/**QUESTION:**
Given a Binary Search Tree (BST), find the minimum value in it.
Example:
8
/
5
/ \
3 6
BST for the given input looks like the above. The minimum value in this BST is `3`.
**APPROACH:**
To find the minimum value in a BST, we can traverse the left child nodes until we reach the leftmost leaf node, which will have the minimum value.
**COMPLEXITY ANALYSIS:**
Let 'n' be the number of nodes in the BST.
- Time Complexity: The time complexity of finding the minimum value in a BST is O(h), where 'h' is the height of the BST. In the worst case, the height of a skewed BST could be 'n', but in a balanced BST, the height is log(n), making the average time complexity O(log n).
- Space Complexity: The space complexity is O(1) as we are not using any extra space.
**CODE:**/
int minVal(Node* root) {
if (!root) return -1;
while (root->left)
root = root->left;
return root->data;
}
2. Practice Problems¶
/**QUESTION:**
Given a Binary Search Tree (BST) and a number `X`, find the Ceil of `X`. Ceil(X) is a number that is either equal to `X` or is immediately greater than `X` in the BST.
If the Ceil of `X` could not be found, return `-1`.
**Example 1:**
Input:
5
/ \
1 7
\
2
\
3
X = 3
Output: 3
Explanation: We find 3 in the BST, so the ceil of 3 is 3.
**APPROACH:**
To find the Ceil of a given number `X`, we can perform a traversal of the BST and keep track of the node with the smallest value that is greater than or equal to `X`.
We can use a recursive function to traverse the BST while updating the answer (`ans`) whenever we find a node with a greater value than `X`. If we find an exact match for `X`, we can directly set `ans` to `X`.
**COMPLEXITY ANALYSIS:**
The time complexity of this approach is O(h), where `h` is the height of the BST. In the worst case, the height of the BST can be `N` (for a skewed tree), where `N` is the number of nodes in the BST.
In the average case, the height is usually log(N) for a balanced BST.
The space complexity is O(1) since we are using a constant amount of extra space (variables) to store the intermediate results.
**CODE:**/
void solve(Node* root, int x, int& ans) {
if (!root) return;
if (root->data == x) {
ans = root->data;
return;
}
if (root->data > x) {
ans = root->data;
return solve(root->left, x, ans);
}
return solve(root->right, x, ans);
}
int findCeil(Node* root, int input) {
if (root == NULL) return -1;
int ans = -1;
solve(root, input, ans);
return ans;
}
// QUESTION:
// Given a Binary Search Tree (BST) with `n` number of nodes and a value `x`, find the greatest value node of the BST which is smaller than or equal to `x`.
// Note: If `x` is smaller than the smallest node of the BST, then return -1.
// APPROACH:
// To find the floor of `x` in the BST, we can perform a recursive traversal of the tree starting from the root. While traversing, we compare the value of the current node with `x` to find the largest value in the tree that is smaller than or equal to `x`. We update the `ans` variable with the current node's value if it is smaller than or equal to `x` and continue the traversal in the left or right subtree.
// Complexity Analysis
// Time complexity: O(h), where h is the height of the BST. In the worst case, the function needs to traverse the entire height of the BST.
// Space complexity: O(1), as the function uses a single integer variable (`ans`) to store the result.
// CODE:-
int findFloor(Node* root, int x) {
if (!root) return -1;
int ans = -1;
while (root) {
if (root->data == x) {
ans = root->data;
break;
} else if (root->data < x) {
ans = root->data;
root = root->right;
} else {
root = root->left;
}
}
return ans;
}
/*
Question:
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example 1:
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
*/
/*
Approach:
1. To insert a value 'val' into the BST, we start from the root node and traverse down the tree to find the appropriate position for insertion.
2. If the BST is empty (i.e., root is null), we create a new node with value 'val' and make it the root of the BST.
3. If the value of the current node is less than 'val', we move to the right subtree, as the value to be inserted will be greater than the current node.
4. If the value of the current node is greater than or equal to 'val', we move to the left subtree, as the value to be inserted will be less than or equal to the current node.
5. We continue this process of traversing down the tree until we reach a leaf node where we can insert the new value 'val'.
Complexity Analysis
Time complexity: O(h), where h is the height of the BST. In the worst case, the function needs to traverse the entire height of the BST to find the appropriate position for insertion.
Space complexity: O(h), where h is the height of the BST. In the worst case, the function may have to traverse the entire height of the BST, leading to h recursive calls in the call stack.
CODE:-
*/
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
else root->left = insertIntoBST(root->left, val);
return root;
}
/*
Question:
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
1. Search for a node to remove.
2. If the node is found, delete the node.
Approach:
To delete a node with a given key from the BST, we need to search for the node first. If the node is found, there are three possible cases:
1. The node to be deleted is a leaf node (no children).
2. The node to be deleted has only one child (left or right child).
3. The node to be deleted has both left and right children.
For the first case, we simply remove the node from the tree and return NULL as the new root.
For the second case, we return the non-NULL child of the node to be deleted as the new root.
For the third case, we find the maximum value node in the left subtree of the node to be deleted (the rightmost node of the left subtree), copy its value to the node to be deleted, and then recursively delete the maximum value node in the left subtree.
Example:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
*/
// Time Complexity: O(log n) on average, O(n) in the worst case, where n is the number of nodes in the BST.
// The time complexity of the delete operation in a BST depends on the height of the tree, which is log n on average for a balanced BST. However, in the worst case, when the BST is skewed (all nodes have only one child), the time complexity becomes O(n).
// Space Complexity: O(log n) on average, O(n) in the worst case.
// The space complexity is determined by the recursion stack during the delete operation. In the average case, the maximum recursion depth is log n for a balanced BST. In the worst case, when the BST is skewed, the recursion depth becomes n.
// CODE:-
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return NULL;
if (root->val == key) {
if (!root->left && !root->right) return NULL; // Case: Node to be deleted is a leaf node
if (!root->left || !root->right) return root->left ? root->left : root->right; // Case: Node to be deleted has only one child
TreeNode* temp = root->left; // Case: Node to be deleted has both left and right children
while (temp->right != NULL) temp = temp->right;
root->val = temp->val;
root->left = deleteNode(root->left, temp->val); // Delete the node that was copied into the current node
}
if (root->val < key) root->right = deleteNode(root->right, key);
root->left = deleteNode(root->left, key);
return root;
}
/*
Question:
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Example:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Approach:
To find the kth smallest value in a binary search tree (BST), we can perform an in-order traversal of the BST and keep track of the count of nodes visited so far. When the count becomes equal to k, we have found the kth smallest value.
1. Perform in-order traversal of the BST.
2. While traversing, keep track of the count of nodes visited and compare it with k.
3. When count becomes equal to k, store the value of the current node as the answer.
Example:
Consider the BST [3, 1, 4, null, 2].
3
/ \
1 4
\
2
In-order traversal of this BST gives: 1, 2, 3, 4. The 1st smallest value is 1, 2nd smallest value is 2, 3rd smallest value is 3, and so on.
Time Complexity: O(log n + k)
- The in-order traversal of a balanced BST takes O(log n) time on average.
- Finding the kth smallest value takes O(k) time in the worst case when k is close to n (the number of nodes in the BST).
- In the worst case, the total time complexity becomes O(log n + k).
Space Complexity: O(log n)
- The space complexity is determined by the recursion stack during the in-order traversal, which has a maximum depth of log n for a balanced BST.
CODE:-
*/
void inorder(TreeNode* root, int k, int& cnt, int& ans) {
if (!root) return;
inorder(root->left, k, cnt, ans);
cnt++;
if (cnt == k) {
ans = root->val;
return;
}
inorder(root->right, k, cnt, ans);
}
int kthSmallest(TreeNode* root, int k) {
int ans = -1, cnt = 0;
inorder(root, k, cnt, ans);
return ans;
}
/*
Question:
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Approach:
- Initialize the range with LONG_MIN and LONG_MAX values.
- Now, if a node->val is out of the range then it's not a BST
- And, then check for the left and right subtrees with modified range
Time Complexity: O(n)
- The in-order traversal visits each node exactly once, where n is the number of nodes in the binary tree.
Space Complexity: O(h)
- The space complexity is determined by the recursion stack during the in-order traversal, where h is the height of the binary tree.
- In the worst case, the height of the binary tree can be n for a skewed tree, so the space complexity becomes O(n).
- However, for a balanced BST, the height is log n, so the space complexity becomes O(log n).
*/
bool solve(TreeNode* root, long low, long high){
if(!root) return true;
if(root->val >= high || root->val <= low) return false;
return solve(root->left,low,(long)root->val) && solve(root->right,(long)root->val,high);
}
bool isValidBST(TreeNode* root) {
if(!root) return true;
return solve(root,LONG_MIN,LONG_MAX);
}
/*
Question:
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Approach:
- Traverse the BST from the root.
- If both the nodes p and q are smaller than the current node's value, then the LCA must be in the left subtree. So, recursively call the function on the left subtree.
- If both the nodes p and q are greater than the current node's value, then the LCA must be in the right subtree. So, recursively call the function on the right subtree.
- If the current node's value is between the values of nodes p and q, then the current node is the LCA.
Time Complexity: O(h)
- h is the height of the BST.
- In the worst case, the height of the BST can be n for a skewed tree, so the time complexity becomes O(n).
- However, for a balanced BST, the height is log n, so the time complexity becomes O(log n).
Space Complexity: O(h)
- The space complexity is determined by the recursion stack during the function call.
- In the worst case, the height of the BST can be n for a skewed tree, so the space complexity becomes O(n).
- However, for a balanced BST, the height is log n, so the space complexity becomes O(log n).
*/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if ((p->val < root->val) && (q->val < root->val)) {
return lowestCommonAncestor(root->left, p, q);
}
if ((p->val > root->val) && (q->val > root->val)) {
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
/*
Question:
Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.
It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.
A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.
A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.
Example:
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Approach:
- The first element of the preorder traversal is the root of the BST.
- We start with the first element of the preorder traversal and recursively build the BST as follows:
- If the current element is greater than the previous element, it must be the right child of the previous element. We build the right subtree of the previous element using this information and recursively move forward in the preorder array.
- If the current element is smaller than the previous element, it must be a left child of one of the previous elements. We keep on traversing the preorder array until we find an element greater than the current element. This element will be the right child of one of the ancestors of the current element.
Time Complexity: O(n)
- In the worst case, we might need to traverse the entire preorder array to construct the BST.
Space Complexity: O(h)
- The space complexity is determined by the recursion stack during the function call.
- In the worst case, the height of the BST can be n for a skewed tree, so the space complexity becomes O(n).
- However, for a balanced BST, the height is log n, so the space complexity becomes O(log n).
*/
TreeNode* solve(int& index, vector<int>& pre, int bound) {
if (index >= pre.size() || pre[index] > bound) {
return NULL;
}
TreeNode* root = new TreeNode(pre[index++]);
root->left = solve(index, pre, root->val);
root->right = solve(index, pre, bound);
return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
int i = 0;
return solve(i, preorder, INT_MAX);
}
/*
Question:
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):
BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Approach:
- We are using a stack to keep track of the nodes during the in-order traversal of the BST.
- In the constructor, we initialize the stack by pushing all the leftmost nodes in the BST to the stack.
- The next() function returns the top element of the stack (which will be the next smallest element in the BST) and pops it from the stack.
- If the node has a right child, we push all the leftmost nodes in the right subtree to the stack before returning the node's value.
- The hasNext() function simply checks if the stack is empty or not.
Time Complexity:
- The constructor takes O(h) time, where h is the height of the BST, as it traverses the leftmost path in the BST.
- The next() and hasNext() functions take O(1) time as they only perform stack operations.
Space Complexity:
- The space complexity is O(h), where h is the height of the BST, as the stack stores the nodes in the leftmost path of the BST.
*/
stack<TreeNode*> st;
BSTIterator(TreeNode* root) {
pushLeft(root);
}
void pushLeft(TreeNode* root) {
while (root) {
st.push(root);
root = root->left;
}
}
int next() {
TreeNode* ans = st.top();
st.pop();
if (ans->right) {
pushLeft(ans->right);
}
return ans->val;
}
bool hasNext() {
return (!st.empty());
}
/*
Question:
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
Explanation:
- We are using two stacks, one for the left traversal and one for the right traversal of the BST.
- The next() function returns the next smallest element in the BST by popping the top element from the left stack and pushing all the leftmost nodes in its right subtree to the stack.
- The before() function returns the next largest element in the BST by popping the top element from the right stack and pushing all the rightmost nodes in its left subtree to the stack.
- We use the two pointer approach with the next() and before() functions to find the pair of elements in the BST whose sum is equal to k.
Time Complexity:
- The findTarget() function uses two pointers (one for the left and one for the right traversal of the BST) and performs a two pointer traversal of the BST, taking O(n) time, where n is the number of nodes in the BST.
- The next() and before() functions take O(h) time each, where h is the height of the BST, as they traverse the leftmost and rightmost paths in the BST.
Space Complexity:
- The space complexity is O(h), where h is the height of the BST, as the stacks store the nodes in the leftmost and rightmost paths of the BST.
*/
stack<TreeNode*> stl;
stack<TreeNode*> str;
void pushLeft(TreeNode* root) {
while (root) {
stl.push(root);
root = root->left;
}
}
void pushRight(TreeNode* root) {
while (root) {
str.push(root);
root = root->right;
}
}
int next() {
if (stl.empty()) return 1e9;
TreeNode* ans = stl.top();
stl.pop();
if (ans->right) {
pushLeft(ans->right);
}
return ans->val;
}
int before() {
if (str.empty()) return 1e9;
TreeNode* ans = str.top();
str.pop();
if (ans->left) {
pushRight(ans->left);
}
return ans->val;
}
bool findTarget(TreeNode* root, int k) {
pushLeft(root);
pushRight(root);
int l = next();
int r = before();
while (l < r) {
if (l == 1e9 || r == 1e9) return false;
if (l + r == k) return true;
else if (l + r < k) l = next();
else r = before();
}
return false;
}
/*
Question:
You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Explanation:
- We perform an in-order traversal of the BST to find the two nodes that are swapped.
- During the in-order traversal, we keep track of the previous node and compare it with the current node. If the current node is less than the previous node, then we have found the two swapped nodes.
- We swap the values of the two nodes to recover the BST.
Time Complexity:
- The in-order traversal takes O(n) time, where n is the number of nodes in the BST.
Space Complexity:
- The space complexity is O(h), where h is the height of the BST, as the recursion stack stores the nodes in the leftmost path of the BST.
*/
TreeNode* prev = NULL;
TreeNode* first = NULL;
TreeNode* last = NULL;
void traversal(TreeNode* root) {
if (!root) return;
traversal(root->left);
if (prev && root->val < prev->val) {
if (!first)
first = prev;
last = root;
}
prev = root;
traversal(root->right);
}
void recoverTree(TreeNode* root) {
if (!root) return;
traversal(root);
int temp = first->val;
first->val = last->val;
last->val = temp;
}
/*
Question:
Given a binary tree. Find the size of its largest subtree that is a Binary Search Tree.
Explanation:
- We use a recursive function to traverse the binary tree in a bottom-up manner.
- At each node, we check if the left and right subtrees are binary search trees.
- If the current node satisfies the binary search tree condition (i.e., the value of the current node is greater than the maximum value in the left subtree and less than the minimum value in the right subtree), then we update the size of the largest subtree.
- We return a triplet containing the size of the subtree, the minimum value in the subtree, and the maximum value in the subtree.
Time Complexity:
- The recursive function visits each node once, so the time complexity is O(n), where n is the number of nodes in the binary tree.
Space Complexity:
- The space complexity is O(h), where h is the height of the binary tree, as the recursion stack stores the nodes in the path from the root to the deepest leaf node.
*/
typedef pair<int,pair<int,int>> triplet;
triplet solve(Node* root) {
if (!root) return {0, {INT_MAX, INT_MIN}};
auto lef = solve(root->left);
auto rig = solve(root->right);
if (lef.second.second < root->data && root->data < rig.second.first)
return {lef.first + rig.first + 1, {min(lef.second.first, root->data), max(rig.second.second, root->data)}};
// here we are returning such values so that it bst condition doesn't satisfy upwards
return {max(lef.first, rig.first), {INT_MIN, INT_MAX}};
}
int largestBst(Node *root) {
auto ans = solve(root);
return ans.first;
}