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;
- 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.
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
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
