DS Lab 6 Binary Search Tree (BST) Solved

 

Lab 6
Binary Search Tree (BST)


In this tutorial, we will continue to practice with a new data structure call Binary Search Tree. We will learn some problems of Binary Search Tree:

•     Create a Node of BST

•     Insert a Node to BST

•     Tree traversal

•     Search a key

•     Find minimum key and maximum key

•     Delete the node containing minimum key

•     Delete a Node in BST

1. What is Binary Search Tree?

Binary Search Tree is a data structure which extends from binary tree but it has a rule: ”𝑥.𝑙𝑒𝑓𝑡.𝑘𝑒𝑦 < 𝑥.𝑘𝑒𝑦 ≤ 𝑥.𝑟𝑖𝑔ℎ𝑡.𝑘𝑒𝑦”. Visualizing this rule:

 

Figure 1: Binary search tree



2.     Create a Node of BST
Each node of BST we will define as a class includes: a key, a left node, and a right node. The left node is the node that contains a smaller key, the right node is the node that contains a larger key.

public class Node { Integer key; Node left, right;

public Node(Integer key) { this.key = key;

this.left = this.right = null;

}

}
1

2

3

4

5

6

7

8

9

3.     Insert a Node to BST
When we want to insert a node to BST, always remember the rule of BST: ”the key of the right node is larger and the key of the left node is smaller than the key of the current node”. So when you insert a node to BST not null, it will have the same steps as searching a key in BST.

private Node insert(Node x, Integer key) { if (x == null) return new Node(key);

int cmp = key.compareTo(x.key); if (cmp < 0)

x.left = insert(x.left, key);

else if (cmp 0)

x.right = insert(x.right , key);

else

x.key = key;

return x;

}
1

2

3

4

5

6

7

8

9

10

11

12

4.     Tree traversal
We have 3 ways to traverse a tree: pre-order, in-order, and post-order. In this section, we will traverse and print the key of each node in the tree. Depend on which way that we have chosen, the output will be different.

4.1.     Pre-order
Pre-order (or node-left-right): In this way, the value of the current node will be printed first, then the left subtree of the current node will be traversed next and finally for the right subtree. This process will be performed recursively for all nodes in the tree.

public void NLR(Node x) { if (x != null) {

System.out.print(x.key + " ");

NLR(x.left);

NLR(x.right);
1

2

3

4

5

}
}
6

7

 

Figure 2: Pre-order

4.2.     In-order
In-order (or left-node-right): In this traversing method, the left subtree of the current node is traversed first, then the value of the current node is printed and finally the right subtree is traversed. This process will be performed recursively for all nodes in the tree.

 

Figure 3: In-order

public void LNR(Node x) {

//code here }
1

2

3

4.3.     Post-order
Post-order (or left-right-node): In this method, the left subtree of the current node will be traversed first, then the right subtree will be traversed next and finally the value of the current node will be printed. This process will be performed recursively for all nodes in the tree.

 

Figure 4: Post-order

public void LRN(Node x) {

//code here }
1

2

3

5.     Search a key
Since the BST tree has a recursive structure, a tree search is easy performed by a recursive algorithm: If the tree is empty, the searching process return null; If the search key is equal to the key at the root node, the searching process ends with the return result as the root node. Otherwise, we will search (recursively) in the next subtree.

private Node search(Node x, Integer key) { if (x == null) return null;

int cmp = key.compareTo(x.key); if (cmp < 0)

return search(x.left, key)

else if (cmp 0) return search(x.riht, key)

else return x;

}
1

2

3

4

5

6

7

8

9

10

11

6.     Find minimum key and maximum key
Since the rule of BST, we can find the node with minimum value or the maximum value easily. If we want to find the minimum value, we just need to traverse the node from root to left recursively until left is NULL. The node whose left is NULL is the node with minimum value. Likewise, traverse the right to find the node with the maximum value.

 

Figure 5: Find minimum value

 

Figure 6: Find maximum value

private Node min(Node x) { if (x.left == null) return x;

else return min(x.left);

}

private Node max(Node x) {

// code here

}
1

2

3

4

5

6

7

8

9

10

7.     Delete the node containing minimum key
To delete the node containing the smallest key in the tree, we will continue to traverse the left subtree until we find the smallest node. This smallest node is also the node that has no left child tree. Then replace the link from the parent node to the right child tree (if any).

 

Figure 7: Delete the node contains mimimum value

private Node deleteMin(Node x) { if (x.left == null) return x.right;

x.left = deleteMin(x.left); return x;

}
1

2

3

4

5

6

8.     Delete a Node in BST
We will have 3 cases when we want to delete a node in BST.

1.   Node to be deleted is leaf

2.   Node to be deleted has only one child

3.   Node to be deleted has two children

In case (1) and (2), simply replace the node to be deleted with a left or right child node.

In case (3), we find the successor of the node to be deleted. Use the successor to replace the node which we want to delete and delete the successor. The successor can be obtained by finding the minimum value in the right child of the node to be deleted.

 

Figure 8: Delete a node in BST

private Node delete(Node x, Key key) { if (x == null) return null;

int cmp = key.compareTo(x.key); if (cmp < 0)

x.left = delete(x.left, key);

else if (cmp 0)

x.right = delete(x.right , key);

else {

// node with only one child or no child

if (x.right == null) return x.left;

if (x.left == null) return x.right;

// node with two children: Get the successor (smallest in the right subtree) Node t = x; x = min(t.right);

// Delete the successor

x.right = deleteMin(t.right);

// re-link left subtree to the node which was replaced x.left = t.left;
1

2

3

4

5

6

7

8

9 10

11

12

13

14

15

16

17

18

19

20

21

22

23

}
} return x;
24

25

26

9. Exercise

Exercise 1
Based on the sections above, implement a BST class completely and write the main function to check it. (Notice: the functions which giving in the sections above are private so we need to implement the public functions to call them with root node)

Exercise 2
In the class containing the main function, define a function call createTree(String strKey). Giving a string of integers (separated by a space character), this function will create a BST tree with the keys of integers following the input string.

Exercise 3

Write the function that prints on the screen the values of the tree in ascending order.

Exercise 4
Write the function that prints on the screen the values of the tree in descending order.

Exercise 5
Write contains function with input is a key, the function returns true if the key in the tree. Otherwise, it returns false.

public boolean contains(Integer key) {

// your code here

}
1

2

3

Exercise 6
Write the function deleteMax() to delete the node containing maximum value in BST.

public void deleteMax() {

// your code here

}
1

2

3

Exercise 7
Write the function to delete a node in BST, but you must use the predecessor instead of the successor.

public void delete_pre() {

// your code here

}
1

2

3

Exercise 8
Write the function to calculate the height of the BST.

private int height() {

// your code here

}
1

2

3

Exercise 9
Write the function sum(Node x) to calculate the sum of all values of the subtree x.

public Integer sum(Node x) {

// your code here

}
1

2

3

Exercise 10
Write the function sum() to calculate the sum of all values of BST.

public Integer sum() {

// your code here

}
1

2

3