Problem 1: Search in a BST
Problem Statement:
Given a BST and a target value x, determine whether the value exists in the
tree.
Problem Breakdown / Steps:
1. If the tree is empty, return false.
2. Compare the target x with the current node value:
○ If equal → return true.
○ If x < current node → search in left subtree.
○ If x > current node → search in right subtree.
3. Repeat recursively or iteratively until the node is found or a null
node is reached.
Pseudocode (Recursive):
function searchBST(node, x):
if node is NULL:
return false
if node.value == x:
return true
if x < node.value:
return searchBST(node.left, x)
else:
return searchBST(node.right, x)
Pseudocode (Iterative):
function searchBST(node, x):
current = node
while current != NULL:
if current.value == x:
return true
else if x < current.value:
current = current.left
else:
current = current.right
return false
Time Complexity:
● O(H) where H = height of BST.
● Average case: O(log N) for balanced BST.
● Worst case: O(N) for skewed BST.
Space Complexity:
● Recursive: O(H) due to recursion stack.
● Iterative: O(1) constant space.
Problem 2: Insert in a BST
Problem Statement:
Given a BST and a value x, insert x into the tree while maintaining the BST
property.
Problem Breakdown / Steps:
1. If the tree is empty, create a new node with value x and return it.
2. Compare x with the current node value:
○ If x < current node → insert into left subtree.
○ If x > current node → insert into right subtree.
○ (For standard BST, ignore duplicates.)
3. Recursively repeat until reaching a null position where the new node
can be attached.
Pseudocode (Recursive):
function insertBST(node, x):
if node == NULL:
return new Node(x)
if x < node.value:
node.left = insertBST(node.left, x)
else if x > node.value:
node.right = insertBST(node.right, x)
return node
Pseudocode (Iterative):
function insertBST(root, x):
if root == NULL:
return new Node(x)
current = root
while true:
if x < current.value:
if current.left == NULL:
current.left = new Node(x)
break
current = current.left
else if x > current.value:
if current.right == NULL:
current.right = new Node(x)
break
current = current.right
return root
Time Complexity:
● O(H) where H = height of BST.
● Average case (balanced BST): O(log N)
● Worst case (skewed BST): O(N)
Space Complexity:
● Recursive: O(H) due to recursion stack.
● Iterative: O(1) constant space.
Problem 3: Delete a Node in BST
Problem Statement:
Given a BST and a value x, delete the node with value x while maintaining
the BST property.
Problem Breakdown / Steps:
1. Search for the node with value x in the BST using the standard BST
traversal:
○ If x < node.value → go to left subtree.
○ If x > node.value → go to right subtree.
2. Node deletion has three cases:
○ Leaf Node (no children): Remove it directly.
○ One Child: Replace the node with its child.
○ Two Children:
■ Find the inorder successor (smallest node in right subtree)
or inorder predecessor (largest node in left subtree).
■ Copy its value to the current node.
■ Recursively delete the successor/predecessor node.
3. Return the updated root after deletion.
Pseudocode (Recursive):
function deleteBST(node, x):
if node == NULL:
return NULL
if x < node.value:
node.left = deleteBST(node.left, x)
else if x > node.value:
node.right = deleteBST(node.right, x)
else:
// Node found
if node.left == NULL and node.right == NULL:
return NULL
else if node.left == NULL:
return node.right
else if node.right == NULL:
return node.left
else:
// Node with two children
successor = findMin(node.right)
node.value = successor.value
node.right = deleteBST(node.right, successor.value)
return node
function findMin(node):
while node.left != NULL:
node = node.left
return node
Time Complexity:
● O(H) where H = height of BST.
● Average case: O(log N)
● Worst case (skewed BST): O(N)
Space Complexity:
● Recursive: O(H)
● Iterative deletion is also possible with O(1) space.
Problem 7: Delete a Node in BST
Problem Statement:
Given a Binary Search Tree (BST) and a value key, delete the node with this
value from the BST while maintaining BST properties.
Problem Breakdown / Steps:
1. Search the Node:
○ Traverse the BST recursively to find the node with value key.
2. Deletion Cases:
○ Case 1: Node is a leaf → Simply remove it.
○ Case 2: Node has one child → Replace the node with its child.
○ Case 3: Node has two children →
■ Find the inorder successor (smallest value in the right
subtree) or inorder predecessor (largest in left subtree).
■ Replace the node’s value with the successor/predecessor.
■ Delete the successor/predecessor node recursively.
3. Return:
○ Return the modified root to maintain tree structure.
Pseudocode:
function deleteNode(node, key):
if node == NULL:
return NULL
if key < node.value:
node.left = deleteNode(node.left, key)
else if key > node.value:
node.right = deleteNode(node.right, key)
else: # node.value == key
if node.left == NULL:
return node.right
else if node.right == NULL:
return node.left
else:
successor = findMin(node.right)
node.value = successor.value
node.right = deleteNode(node.right, successor.value)
return node
function findMin(node):
while node.left != NULL:
node = node.left
return node
Time Complexity:
● O(H) where H = height of BST
● Average case (balanced BST): O(log N)
● Worst case (skewed BST): O(N)
Space Complexity:
● Recursive: O(H) due to call stack
● Iterative approach can achieve O(1) auxiliary space