CS 300 – Analysis & Design | Assignment 5-2 – Binary Search Tree |SNHU| – Pseudocode, Reflection, and Complete C++ Code

Assignment 5-2 Binary Search Tree

1. Pseudocode

Insert(bid)

IF root is NULL:

root ← new Node(bid)

ELSE:

CALL addNode(root, bid)

addNode(node, bid)

IF bid.key < node.key:

IF node.left is NULL:

node.left ← new Node(bid)

ELSE:

CALL addNode(node.left, bid)

ELSE:

IF node.right is NULL:

node.right ← new Node(bid)

ELSE:

CALL addNode(node.right, bid)

Search(bidKey)

current ← root

WHILE current is NOT NULL:

IF bidKey == current.key:

RETURN current.bid

ELSE IF bidKey < current.key:

current ← current.left

ELSE:

, current ← current.right

RETURN NULL

Remove(bidKey)

CALL removeNode(root, bidKey)

removeNode(node, bidKey)

IF node is NULL:

RETURN node

IF bidKey < node.key:

node.left ← removeNode(node.left, bidKey)

ELSE IF bidKey > node.key:

node.right ← removeNode(node.right, bidKey)

ELSE:

IF node.left is NULL AND node.right is NULL:

DELETE node

RETURN NULL

IF node.left is NULL:

temp ← node.right

DELETE node

RETURN temp

IF node.right is NULL:

temp ← node.left

DELETE node

RETURN temp

temp ← findMin(node.right)

node.key ← temp.key

node.bid ← temp.bid