KEMBAR78
Binary Search Tree | PDF | Theoretical Computer Science | Algorithms And Data Structures
0% found this document useful (0 votes)
10 views8 pages

Binary Search Tree

Uploaded by

Mithil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
10 views8 pages

Binary Search Tree

Uploaded by

Mithil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

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

You might also like