It is a Saturday morning in the Twin Cities of Minneapolis and St. Paul. It rained last night. Hopefully the day will be dry. I am planning on cooking chicken wings in the gas grill on the deck. There are not too many warm days left to use the grill this season.
A few days ago I started reading chapter four from “Cracking the Coding Interview” by Gayle Laakmann McDowell. For some reason I diverted to adding and deleting values from a BST. I always like to find how others approached the problem. I started watching some videos and reading some articles on the web. Several of the algorithms were convoluted and they seem to fail with different values. So I decided to write some code which seems to work as expected. If you give it a try and find issues please let me know.
I wrote some Java code using the Eclipse IDE. As soon as I get a copy of MS Word and Visio on my newest machine will start using Microsoft Visual Studio Code and posting directly from it.
Let’s start by taking a look at the test scaffolding.
/*
* Test scaffolding.
*/
public static void main(String[] args) throws Exception {
// **** value to insert or delete from BST ****
int val = 0;
// **** ****
boolean found;
// **** create the BST ****
BST tree = new BST();
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** get number of operations ****
int n = sc.nextInt();
// **** flush rest of line ****
sc.nextLine();
// **** loop performing operations in the BST ****
for ( ; n > 0; n--) {
// **** read the next line from the input ****
String line = sc.nextLine();
// **** split the line ****
String s[] = line.split(" ");
// **** extract the val ****
val = Integer.parseInt(s[1]);
// **** perform this operation in the BST ****
switch (s[0]) {
// **** insert value into BST ****
case "i":
// ???? ????
System.out.println("main <<< i " + val);
// **** insert value into BST ****
tree.insert(tree.root, val);
// **** traverse the BST in order ****
tree.inOrderBST(tree.root);
// **** find this value in the BST ****
found = tree.find(tree.root, val);
if (found == false)
throw new Exception("inserted value: " + val + " was NOT found");
break;
// **** delete value from BST ****
case "d":
// ???? ????
System.out.println("main <<< d " + val); // **** delete value from BST **** tree.root = tree.delete(tree.root, val); // **** traverse the BST in order **** tree.inOrderBST(tree.root); // **** attempt to find this value in the BST **** found = tree.find(tree.root, val); if (found == true) throw new Exception("deleted value: " + val + " was found"); break; // **** unexpected operation **** default: throw new Exception("invalid operation s[0] ==>" + s[0] + "<==");
}
}
// **** close scanner ****
sc.close();
}
We first create an empty BST. We then open a scanner to be able to read data from the console.
The operations are expressed by a letter (I for insert and d for delete) followed by a value (an integer in this case). The first value in the sequence is the number of operations to execute. The number is followed by pairs of letter and integer specifying the operation and associated value.
We loop once per operation. After parsing the line we select the operation to perform. We then display the operation followed by the value.
For inserts we insert the value and traverse the BST in order to provide a visual of the contents of the BST. We then attempt to find the inserted value in the BST. If the value is not found we throw an exception.
For deletes we first delete the value from the BST, we then traverse the BST in order and finally we check if the value we just inserted is not found in the BST.
For completeness we check for unexpected operations and finally we close the scanner.
1 d 99 main <<< d 99 inOrderBST <<<
In this example we attempt to delete a value from an empty BST. The value is not found. All is well.
2 i 11 d 11 main <<< i 11 inOrderBST <<< 11 main <<< d 11 inOrderBST <<<
We now tried to insert a value and then delete it from the BST. After the value is inserted we see in the in order traversal that the value is in the tree. After deleting the value the in order traversal indicates that the BST is empty as expected. Note that the checks for finding values in the BST also worked as expected.
23 i 11 i 6 i 8 i 19 i 4 i 10 i 5 i 17 i 43 i 49 i 31 d 11 d 43 d 4 d 10 d 49 d 8 d 6 d 5 d 19 d 31 d 17 d 99 main <<< i 11 inOrderBST <<< 11 main <<< i 6 inOrderBST <<< 6 11 main <<< i 8 inOrderBST <<< 6 8 11 main <<< i 19 inOrderBST <<< 6 8 11 19 main <<< i 4 inOrderBST <<< 4 6 8 11 19 main <<< i 10 inOrderBST <<< 4 6 8 10 11 19 main <<< i 5 inOrderBST <<< 4 5 6 8 10 11 19 main <<< i 17 inOrderBST <<< 4 5 6 8 10 11 17 19 main <<< i 43 inOrderBST <<< 4 5 6 8 10 11 17 19 43 main <<< i 49 inOrderBST <<< 4 5 6 8 10 11 17 19 43 49 main <<< i 31 inOrderBST <<< 4 5 6 8 10 11 17 19 31 43 49 main <<< d 11 inOrderBST <<< 4 5 6 8 10 17 19 31 43 49 main <<< d 43 inOrderBST <<< 4 5 6 8 10 17 19 31 49 main <<< d 4 inOrderBST <<< 5 6 8 10 17 19 31 49 main <<< d 10 inOrderBST <<< 5 6 8 17 19 31 49 main <<< d 49 inOrderBST <<< 5 6 8 17 19 31 main <<< d 8 inOrderBST <<< 5 6 17 19 31 main <<< d 6 inOrderBST <<< 5 17 19 31 main <<< d 5 inOrderBST <<< 17 19 31 main <<< d 19 inOrderBST <<< 17 31 main <<< d 31 inOrderBST <<< 17 main <<< d 17 inOrderBST <<<
In this last screen capture we perform several operations. We first insert some values and delete them in a different order. Note that the last operation is to delete value 99 which was never inserted. All checks appear to be working as expected.
Before we look into the rest of the implementation I would like to cover how to delete values from a BST. The last diagram shows three views of the BST after inserting the same nodes as we used in the last screen capture and performing a delete operation.
In the InitialBST diagram we decide to delete 11 from the BST. In a BST we must have a root node in which all values on the left child are smaller (<=) and all values on the right child are bigger (>). We are faced with two options to replace the value in the node we wish to delete. We can use the predecessor on the left sub tree or the successor on the right sub tree.
The predecessor of 11 (colored in red) in our example is 10 (colored in blue) while the successor is 17 (colored in orange). Our algorithm could decide on using a method to find the predecessor or one to find the successor.
The second diagram illustrates that we replaced 11 with 10. We used the method to find the predecessor. We will shortly see the code. Note that in this diagram we also have node 43 in red, node 31 in blue and node 49 in orange. If you refer back to the set of operations we are performing in our BST, the second delete operation removes value 43 form our BST.
The last diagram goes back to the first one in which we decide to delete value 11 but we now use in our code a method that selects the successor which in this case is 17. Note that the properties of the BST are retain is we choose to replace 11 with 10 or 17. The BSTs are different but both are valid.
/*
* Node class
*/
class Node {
// **** ****
public int val;
public Node left;
public Node right;
// **** constructor ****
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
The Node class is quite simple and very typical. A node has a value and two children. Note that a node may have 2, 1 or 0 children. The only method we need is a constructor.
/*
* BST class
*/
public class BST {
// **** ****
Node root;
// **** BST constructor ****
public BST() {
this.root = null;
}
// ???? more code follows ????
}
The BST class has more methods a root node and a constructor. We will cover them later in this post.
The two methods of interest are insert and delete.
// **** insert node into BST ****
public void insert(Node root, int val) {
// **** add this node as the root of the BST ****
if (root == null) {
root = new Node(val);
this.root = root;
return;
}
// **** deal with the left child ****
if (val <= root.val) {
if (root.left == null) {
root.left = new Node(val);
return;
} else {
insert(root.left, val);
}
}
// **** deal with the right child ****
else {
if (root.right == null) {
root.right = new Node(val);
return;
}
else {
insert(root.right, val);
}
}
}
Since we started by defining our BST as an empty Node, we need to take care of the case when we insert a node into an empty tree. We then deal with inserting the value on the left sub tree if it is less than or equal to the value in the current root. If the left child is null then we create a new Node and attach it to the left child. If the left child is present in the BST we recursively call insert with the left child.
The treatment of the right child is quite similar. If the right child is null we create a new Node with the desired value. If the right child is available, we recursively call insert on the right child sub tree.
// **** search for node and delete it from the BST ****
public Node delete(Node root, int val) {
// **** check for a null root ****
if (root == null) {
return root;
}
// **** search for the node on the left side of the BST ****
if (val < root.val) { root.left = delete(root.left, val); } // **** search for the node on the right side of the BST **** else if (val > root.val) {
root.right = delete(root.right, val);
}
// **** found node to delete ****
else {
// **** node to delete has both children ****
if ((root.left != null) && (root.right != null)) {
// **** save the root (being deleted) ****
Node temp = root;
// // **** find the in order predecessor (max val on left tree) (A) ****
// Node node = inOrderPredecessor(temp.left);
// **** find the in order successor (min val on right tree) (B) ****
Node node = inOrderSuccessor(temp.right);
// **** replace the value of the root with one from the node ****
root.val = node.val;
// // **** delete the node (with A) ****
// delete(root.left, node.val);
// **** delete the node (with B) ****
root.right = delete(root.right, root.val);
}
// **** node to delete only has a right child ****
else if (root.left == null) {
return root = root.right;
}
// **** node to delete only has left child ****
else if (root.right == null) {
return root = root.left;
}
}
// **** return root node ****
return root;
}
This operation is more interesting yet is quite simple. We need to find the node with the value that we need to delete. As you can see we accomplish this by recursively looking for the value on the left and on the right sub trees depending on the value.
Once the value is located we have three cases we need to address. The node is a leaf node (no children), the node has one child (it can be the left or right child) and the other possible case is when the node has two children. This is why we attempted deleting the value in the root and then the value in a sub tree with two children.
These three cases are handled in the code. Note that I have commented out a couple lines in the method. In the commented out code we replace the value of the node we wish to delete with the predecessor which would be in the left sub tree. We also have to delete the value so we do not end up with a duplicate. The same holds true is we wish to use the successor.
// **** find the in order predecessor (max value) ****
public Node inOrderPredecessor(Node root) {
if (root.right == null)
return root;
else return inOrderPredecessor(root.right);
}
// **** find the in order successor (min value) ****
public Node inOrderSuccessor(Node root) {
if (root.left == null)
return root;
else
return inOrderSuccessor(root.left);
}
The inOrderPredecessor method is used to locate the in order predecessor value for the value we wish to delete from the BST. Note that such value would be found in the left sub tree.
The inOrderSuccessor method is used to locate the in order successor value for the value we wish to delete from the BST. Note that such value would be found in the right sub tree.
Referring back to the first BST diagram when we wish to delete 11 from the BST, if we choose to use the predecessor we need to find 10 in the left sub tree (10 is the predecessor in this BST to 11). If we decide to use the successor, we then need to search for 17 in the right sub tree (17 is the successor of 11 in our sample BST).
// **** find node in BST ****
public boolean find(Node root, int v) {
// **** ****
boolean found = false;
// **** ****
if (root != null) {
// **** check the value of the root ****
if (v == root.val)
return true;
// **** check left child (if needed) ****
if (v < root.val)
found = find(root.left, v);
// **** check right child ****
else
found = find(root.right, v);
} else
return false;
// **** ****
return found;
}
// **** ****
public void inOrderBST(Node root) {
System.out.print("inOrderBST <<< ");
inOrder(root);
System.out.println();
}
// **** traverse BST in order ****
private void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
// System.out.println("inOrder <<< val: " + node.val);
System.out.print(node.val + " ");
inOrder(node.right);
}
}
// **** traverse BST in pre order ****
public void preOrder(Node node) {
if (node != null) {
System.out.println("preOrder <<< val: " + node.val);
preOrder(node.left);
preOrder(node.right);
}
}
// **** traverse BST in post order ****
public void postOrder(Node node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.println("postOrder <<< val: node.val");
}
}
The find method is used to find a value in the BST. We wish to verify that we can find the last value we inserted into our BST. The same method is used after deleting a value from the BST. We want to verify that the value is no longer in our BST.
The preOrder and postOrder methods are not used in the current examples. I put them in for completeness and to verify the operations of the insert and delete methods. Note that they display the values one line at a time.
I did use the inOrder method but decided to change it so all values could be displayed on a single line. I made the method private and changed the way the value is displayed. I also had to add the inOrderBST method that handles the header and calls the inOrder method recursively to display the values in the BST.
The entire code for this project can be found in my GitHub repository.
On my next posts I will continue to cover problems from the “Cracking the Coding Interview” and my experimentation with the Kinect camera and Python language using the Microsoft Azure cloud.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa