Binary search tree Flashcards
Recursive approach to implement search operation in BST
// Node class to represent each element in the BST
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
private boolean searchRec(Node root, int data) {
// Base cases: root is null or data is present at root
if (root == null || root.data == data)
return root != null;
// Recursively search left or right subtree
if (data < root.data)
return searchRec(root.left, data);
return searchRec(root.right, data);
}
Iterative approach to implement BST
public class BinarySearchTree {
// Definition of a tree node
static class TreeNode {
int value;
TreeNode left, right;
public TreeNode(int value) {
this.value = value;
left = right = null;
}
}
// Iterative search method
public static boolean search(TreeNode root, int target) {
TreeNode current = root;
while (current != null) {
if (current.value == target) {
return true; // Found the target
} else if (target < current.value) {
current = current.left; // Move to the left subtree
} else {
current = current.right; // Move to the right subtree
}
}
return false; // Target not found
}
// Main method to test the search operation
public static void main(String[] args) {
// Create a sample BST
TreeNode root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(40);
root.right.left = new TreeNode(60);
root.right.right = new TreeNode(80);
// Test the search operation
int target = 40;
if (search(root, target)) {
System.out.println("Value " + target + " found in the BST.");
} else {
System.out.println("Value " + target + " not found in the BST.");
}
}
}
Explanation
-
TreeNode Class: Represents a node in the BST with
value,left, andrightfields. -
Iterative Search:
- Starts at the root node.
- Compares the target value with the current node’s value.
- If the target is less, moves to the left subtree; otherwise, moves to the right subtree.
- If the target matches the current node’s value, returns
true. - If the target cannot be found and the traversal ends, returns
false.
- Time Complexity: ( O(h) ), where ( h ) is the height of the BST.
- Space Complexity: ( O(1) ), as no extra space is used except for variables.
This method avoids the potential stack overflow issues that a recursive approach might face with very deep trees.
definition of BST
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
Search a node in BST
Given a Binary Search Tree and a node value X, find if the node with value X is present in the BST or not.
Example 1:
Input: 2
\
81
/ \
42 87
\ \
66 90
/
45
X = 87
Output: 1
Explanation: As 87 is present in the
given nodes , so the output will be
1.
Example 2:
Input: 6
\
7
/ \
8 9
X = 11
Output: 0
Explanation: As 11 is not present in
the given nodes , so the output will
be 0.
Your Task:
You don’t need to read input or print anything. Complete the functionsearch()which returns true if the node with value x is present in the BSTelse returns false.
Expected Time Complexity:O(Height of the BST)
Expected Auxiliary Space:O(1).
If data at current node is equal to x, return true.
If data at the current node is less than given value, call the function recursively to search in right subtree.
Else call the function recursively to search in left subtree.
bool search(Node* root, int x) {
// base case
if (root == NULL) return false;
// if data at current node is equal to x, we return true.
if (root->data == x) return true;
// if data at the current node is less than given value, we call the
// function recursively to search in right subtree.
if (root->data < x) return search(root->right, x);
// else we call the function recursively to search in left subtree.
return search(root->left, x);
}
Insert a node in a BST
Given a BST and a key K. If K is not present in the BST, Insert a new Node with a value equal to K into the BST.
Note: If K is already present in the BST, don’t modify the BST.
Example 1:
Input:
2
/ \
1 3
K = 4
Output: 1 2 3 4
Explanation: After inserting the node 4
Inorder traversal will be 1 2 3 4.
Example 2:
Input:
2
/ \
1 3
\
6
K = 4
Output: 1 2 3 4 6
Explanation: After inserting the node 4
Inorder traversal of the above tree
will be 1 2 3 4 6.
Your Task:
You don’t need to read input or print anything. Your task is to complete the function insert() which takes the root of the BST and Key K as input parameters and returns the root of the modified BST after inserting K.
Note: The generated output contains the inorder traversal of the modified tree.
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(Height of the BST).
If given data is less than data at the current node, call the function recursively to insert new node in left subtree.
Else if given data is more than data at the current node, call the function recursively to insert new node in right subtree.
If it’s equal you simply need to ignore the insertion.
Node* insert(Node* node, int data) {
// if node is null, we return a new node with given data.
if (node == NULL) return new Node(data);
// if given data is less than data at the current node, we call the
// function recursively to insert new node in left subtree.
if (data ( node->data) node->left = insert(node->left, data);
// else if given data is more than data at the current node, we call the
// function recursively to insert new node in right subtree.
else if (data > node->data)
node->right = insert(node->right, data);
return node; }
JS
/**
- @param {Node} node
- @param {number} data
- @returns {Node}
- /
class Solution {
// Function to insert a node in a BST.
insert(node, data) {
// if node is null, we return a new node with given data.
if (node === null) return new Node(data);
// if given data is less than data at the current node, we call the
// function recursively to insert new node in left subtree.
if (data ( node.data) node.left = this.insert(node.left, data);
// else if given data is more than data at the current node, we call the
// function recursively to insert new node in right subtree.
else if (data > node.data)
node.right = this.insert(node.right, data);
return node; } }
Delete a node from BST
Given a Binary Search Tree and a node value X. Delete the node with the given value X from the BST. If no node with value x exists, then do not make any change.
Example 1:
Input:
2
/ \
1 3
X = 12
Output: 1 2 3
Explanation: In the given input there
is no node with value 12 , so the tree
will remain same.
Example 2:
Input:
1
\
2
\
8
/ \
5 11
/ \ / \
4 7 9 12
X = 9
Output: 1 2 4 5 7 8 11 12
Explanation: In the given input tree after
deleting 9 will be
1
\
2
\
8
/ \
5 11
/ \ \
4 7 12
Your Task:
You don't need to read input or print anything. Your task is to complete the function deleteNode() which takes two arguments. The first being the root of the tree, and an integer 'X' denoting the node value to be deleted from the BST. Return the root of the BST after deleting the node with value X. Do not make any update if there's no node with value X present in the BST.
Note: The generated output will be the inorder traversal of the modified tree.
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(Height of the BST).
- You need to take care of three possibilities:
Node to be deleted is leaf
Node to be deleted has only one child
Node to be deleted has two children
Node to be deleted is leaf: Simply remove from the tree.
Node to be deleted has only one child: Copy the child to the node and delete the child
Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
// Function to find the node with minimum element.
Node *minValueNode(Node *nod) {
Node *current = nod;
while (current->left != NULL) current = current->left;
return current;
}
// Function to delete a node from BST.
Node *deleteNode(Node *root, int key) {
// base case
if (root == NULL) return root;
// if given value is less than data at current node, we call function
// recursively to delete in left subtree.
if (key < root->data) root->left = deleteNode(root->left, key);
// else if given value is more than data at current node, we call function
// recursively to delete in right subtree.
else if (key > root->data)
root->right = deleteNode(root->right, key);
// else we need to delete the current node.
else {
// if node is with only one child or no child.
if (root->left == NULL) {
struct Node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node *temp = root->left;
free(root);
return temp;
}
// if node has two children, getting the inorder successor
//(smallest in the right subtree).
struct Node *temp = minValueNode(root->right);
// copying the inorder successor's data to this node.
root->data = temp->data;
// deleting the inorder successor.
root->right = deleteNode(root->right, temp->data);
}
return root;
}
Delete a node from BST
What are the three possibilities that I need to take care of
Node to be deleted is leaf
Node to be deleted has only one child
Node to be deleted has two children
Delete a node from BST
what to do when Node to be deleted is leaf:
simply remove from the tree
Delete a node from BST
what to do when Node to be deleted has only one child:
Copy the child to the node and delete the child
Delete a node from BST
what to do when Node to be deleted has two children:
Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
Delete a node from BST
write code for getting min node
Node *minValueNode(Node *nod) {
Node *current = nod;
while (current->left != NULL) current = current->left;
return current;
}Delete a node from BST
what would be the base case in the delete functions
// base case
if (root == NULL) return root;Delete a node from BST
what would be the next step after the base case when - // if given value is less than data at current node, we call function // recursively to delete in left subtree.
if (key < root->data) root->left = deleteNode(root->left, key);
Delete a node from BST
what would be the next step after this when - // if given value is less than data at current node, we call function // recursively to delete in left subtree.
// else if given value is more than data at current node, we call function
// recursively to delete in right subtree.
else if (key > root->data)
root->right = deleteNode(root->right, key);Delete a node from BST
what would be the next step after this when - // if given value is more than data at current node, we call function // recursively to delete in right subtree.
// else we need to delete the current node.
else {
// if node is with only one child or no child.
if (root->left == NULL) {
struct Node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node *temp = root->left;
free(root);
return temp;
}Delete a node from BST
what would be the next step after this when - // else we need to delete the current node.
// if node has two children, getting the inorder successor
//(smallest in the right subtree).
struct Node *temp = minValueNode(root->right);
// copying the inorder successor's data to this node.
root->data = temp->data;
// deleting the inorder successor.
root->right = deleteNode(root->right, temp->data);
}
return root;
Floor in BST
Given a Binary search tree and a value X, the task is to complete the function which will return the floor of x.
Note: Floor(X) is an element that is either equal to X or immediately smaller to X. If no such element exits return -1.
Example 1:
Input:
8
/ \
5 9
/ \ \
2 6 10
X = 3
Output: 2
Explanation: Floor of 3 in the given BST
is 2
Example 2:
Input:
3
/ \
2 5
/ \
4 7
/
3
X = 1
Output: -1
Explanation: No smaller element exits
Your task:
You don't need to worry about the insert function, just complete the function floor() which should return the floor of X. If no such element exits return -1.
Expected Time Complexity: O(Height of the BST)
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 <= Number of nodes <= 105
1 <= X, Value of Node <= 106
Algorithm:
If data at current node is equal to given number, return it.
If data at current node is greater than given number, call the function recursively for left subtree.
Else data at current node is smaller than given number so call the function recursively for right subtree.
Return floor of given number or -1 if no such element exists.
// Function to find the floor of given number.
int floorUtil(Node* root, int key) {
if (!root) return INT_MAX;
// if data at current node is equal to given number, we return it.
if (root->data == key) return root->data;
// if data at current node is greater than given number, we call
// the function recursively for left subtree.
if (root->data > key) return floorUtil(root->left, key);
// else data at current node is smaller than given number so we call
// the function recursively for right subtree.
int floorValue = floorUtil(root->right, key);
return (floorValue <= key) ? floorValue : root->data; }
// Function to return the floor of given number in BST.
int floor(Node* root, int key) {
int ans = floorUtil(root, key);
// returning floor of given number or -1 if no such element exists.
if (ans == INT_MAX) return -1;
return ans; }
Floor in BST
What is the algorithm for solving this ?
Algorithm:
If data at current node is equal to given number, return it.
If data at current node is greater than given number, call the function recursively for left subtree.
Else data at current node is smaller than given number so call the function recursively for right subtree.
Return floor of given number or -1 if no such element exists.
Floor in BST
Base case for floorUtil function
if (!root) return INT_MAX;
Floor in BST
What we do when // if data at current node is equal to given number
if (root->data == key) return root->data;
Floor in BST
What we do when
if data at current node is greater than given number
we call the function recursively for left subtree.
if (root->data > key) return floorUtil(root->left, key);
Floor in BST
What we do when
data at current node is smaller than given number
we call the function recursively for right subtree.
int floorValue = floorUtil(root->right, key);
return (floorValue <= key) ? floorValue : root->data;
Floor in BST
// Function to return the floor of given number in BST.
int floor(Node* root, int key) {
int ans = floorUtil(root, key);
// returning floor of given number or -1 if no such element exists.
if (ans == INT_MAX) return -1;
return ans; }
Ceil in BST
write the algorithm for this
Algorithm:
If data at current node is equal to given number, return it.
If data at current node is smaller than given number, call the function recursively for right subtree.
Else data at current node is greater than given number so call the function recursively for left subtree.
Return ceil of given number.
Ceil in BST
write the base case for this
// base case
if (root == NULL) return -1;ciel in BST
What we do when
if data at current struct node is equal to given number
we return it.
if (root->data == input) return root->data;
Ciel in BST
What we do when
if data at current struct node is smaller than given number
we call the function recursively for right subtree.
if (root->data < input) return findCeil(root->right, input);
Ciel in BST
What we do when
data at current node is greater than given number
we call the function recursively for left subtree.
int cceil = findCeil(root->left, input);
// returning ceil of given number.
return (cceil >= input) ? cceil : root->data;Ciel in BST
What we do when
data at current node is greater than given number
we call the function recursively for left subtree.
int cceil = findCeil(root->left, input);
What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
O(n) for all
B
O(Logn) for all
C
O(Logn) for search and insert, and O(n) for delete
D
O(Logn) for search, and O(n) for insert and delete
In skewed Binary Search Tree (BST), all three operations can take O(n). See the following example BST and operations.
10
/
20
/
30
/
40
Search 40.
Delete 40
Insert 50.
What is skewed binary search tree ?
A skewed binary tree is a type of binary tree in which all the nodes have only either one child or no child.
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?
A
Inorder Successor is always a leaf node
B
Inorder successor is always either a leaf node or a node with empty left child
C
Inorder successor may be an ancestor of the node
D
Inorder successor is always either a leaf node or a node with empty right child
B
Let X be the node to be deleted in a tree with root as ‘root’. There are three cases for deletion
1) X is a leaf node: We change left or right pointer of parent to NULL (depending upon whether X is left or right child of its parent) and we delete X
2) One child of X is empty: We copy values of non-empty child to X and delete the non-empty child
3) Both children of X are non-empty: In this case, we find inorder successor of X. Let the inorder successor be Y. We copy the contents of Y to X, and delete Y.
Sp we need inorder successor only when both left and right child of X are not empty. In this case, the inorder successor Y can never be an ancestor of X. In this case, the inorder successor is the leftmost node in right subtree of X. Since it is leftmost node, the left child of Y must be empty.
We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? (GATE CS 2011) A 0 B 1 C n! D (1/(n+1)).2nCn
B
There is only one way. The minimum value has to go to the leftmost node and the maximum value to the rightmost node. Recursively, we can define for other nodes.
- How many distinct binary search trees can be created out of 4 distinct keys?
(a) 5
(b) 14
(c) 24
(d) 42
Answer (b)
Here is a systematic way to enumerate these BSTs. Consider all possible binary search trees with each element at the root. If there are n nodes, then for each choice of root node, there are n – 1 non-root nodes and these non-root nodes must be partitioned into those that are less than a chosen root and those that are greater than the chosen root.
Let’s say node i is chosen to be the root. Then there are i – 1 nodes smaller than i and n – i nodes bigger than i. For each of these two sets of nodes, there is a certain number of possible subtrees.
Let t(n) be the total number of BSTs with n nodes. The total number of BSTs with i at the root is t(i – 1) t(n – i). The two terms are multiplied together because the arrangements in the left and right subtrees are independent. That is, for each arrangement in the left tree and for each arrangement in the right tree, you get one BST with i at the root.
Summing over i gives the total number of binary search trees with n nodes.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree? A 7 5 1 0 3 2 4 6 8 9 B 0 2 4 3 1 6 5 9 8 7 C 0 1 2 3 4 5 6 7 8 9 D 9 8 6 4 2 3 0 1 5 7
In-order traversal of a BST gives elements in increasing order. So answer c is correct without any doubt. draw the BST
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004)
A 2
B 3
C 4
D 6
B
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree? A 10, 20, 15, 23, 25, 35, 42, 39, 30 B 15, 10, 25, 23, 20, 42, 35, 39, 30 C 15, 20, 10, 23, 25, 42, 35, 39, 30 D 15, 10, 23, 25, 20, 35, 42, 39, 30
D
Consider the following Binary Search Tree
If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?
A 2.75 B 2.25 C 2.57 D 3.25
Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder A Any one of the given three traversals is sufficient B Either 2 or 3 is sufficient C 2 and 3 D 1 and 3
B
When we know either preorder or postorder traversal, we can construct the BST. Note that we can always sort the given traversal and get the inorder traversal. Inorder traversal of BST is always sorted.
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this? A O(Logn) B O(n) C O(nLogn) D none of the above, as the tree cannot be uniquely determined.
One important thing to note is, it is Binary Search Tree, not Binary Tree. In BST, inorder traversal can always be obtained by sorting all keys.
Same technique can be used for postorder traversal.
