Student Name: Student’s ID:

CSD201 – Binary Search Tree Implementation

Question 1.
1. Draw all possible binary search trees for the data elements 5, 9, and 12.
2. Create a binary search tree using the following data entered as a sequential set:
14 3 7 10 33 56 80 66 70
3. Delete the node root node from the binary search tree in Exercise 1, draw the tree.
4. Draw the memory space when the tree in Exercise 1 is stored at physical level. Suppose that the root
node address is 0xAABBFAFA. Other addresses are random.
Question 2. Fill in the blanks (…) to implement the following methods in of the BST:
a. Find the node containing the smallest Key in BST: d. Find the node containing Key=x in BST:
Algorithm findSmallestBST (root <Node>) Algorithm searchBST (root <Node>,
//Finds the smallest node in a BST arg <key>)
//Pre: root is the root of a non-empty BST //Searches a binary search tree for a given value
//Return: address of smallest node //Pre: root is the root of a non-empty BST,
1. if (……………………….) // arg is the key value requested
return (root) //Return: the node address if the value is found,
2. return findSmallestBST (………………) // null otherwise
End findSmallestBST 1. if (…………………….)
b. Find the node containing the largest Key in BST: return null
Algorithm findLargestBST (root <Node>) 2. else if (arg = root.key)
//Finds the largest node in a BST return ……………
//Pre: root is the root of a non-empty BST 3. else if (arg < root.key)
//Return: address of largest node …………………………………………...
1. if (…………………………..) 4. else if (arg > root.key)
return (root) ……………………………………………
2. return findLargestBST (………………..) 5. else
End findLargestBST return null
c. Execute the question a) on the following BST: End searchBST

e. Execute the question d) on the tree in

question c)

Question 3. Recursion on BST

1. Write a function that counts the total nodes of a BST with prototype as below:
Algorithm Count_Node(subroot <Node>)
2. Write a function that counts the total leaf nodes of a BST with prototype as below:
Algorithm Count_Leaf(subroot <Node>)
3. Write a function that counts the level of a BST with prototype as below:
Algorithm Count_Heigh(subroot <Node>)
Question 4. Interview Questions: Write a function that checks whether a binary tree is a binary
search tree or not.
Question 5. Fill in the blanks:
a. Non-Recursive b. Recursive
Algorithm insertBST (root <Node>,
new <Node>) Algorithm insertBST (root <Node>,
//Inserts a new node into BST using iteration new <Node>)
//Pre: root is the root of a non-empty BST // Inserts a new node into BST using recursion
new is address of the new node //Pre: root is the root of a non-empty BST
//Post: new node inserted into the tree new is the new node
1. if (root = null) //Post: new node inserted into the tree
………………… 1. if (root = null)
2. else root = new
1. pWalk = root 2. else
2. loop (pWalk not null) 1. if (new.key < root.key)
1. parent = pWalk ………………………………………..
2. if (new.key < pWalk.key) 2. else
………………………………..... ………………………...................
3. else 3. return
…………………………………... End insertBST
Location found for the new node
3. if (new.key < parent.key)
…………………………………… d. Execute the question b) when insert
4. else key=22 into the BST below:
…………………………………...
3. return
End insertBST
c. Execute the question a) when insert key=19 into
the BST below:

Question 6. Delete a note from a BST:

a. Algorithm b. Execute
Algorithm deleteBST ( ref root <Node>, Execute the question a when delete the node
val dltKey <key>) containing the key =22 from the BST below:
//Deletes a node from a BST
//Pre: root is a pointer to a non-empty BST
dltKey is the key of the node to be deleted
//Post: node deleted & memory recycled
if dltKey not found, root unchanged
//Return: true if node deleted; false otherwise
1 if (root = null)
Return;
2 if (dltKey < root.data.key)
deleteBST (root.left, dltKey)
3 else if (dltKey > root.data.key)
……………………………………………. Suppose that we choose the largest node of
4 else //Deleted node found
leftchild to replace the deleted node.
 1. if (root.left = null) c. Hãy viết lại đoạn mã của câu a) cho trường
1. dltPtr = root hợp chọn nút bé nhất bên nhánh phải để thay cho
2. root = root.right một nút bị xóa. Minh họa đoạn mã vừa viết với
3. recycle (dltPtr)
BST như của câu b (nút cần xóa vẫn là 18).
4. return true
2. else if (root.right = null)
1. ……………………..
2. ……………………..
3. ……………………..
4. return true
3. else
1. dltPtr = root.left
2. loop (dltPtr.right not null)
1. dltPtr = dltPtr.right
3. ………………………………………………
4. return deleteBST (……………………………..)
End deleteBST