BINARY SEARCH TREES: INSERTION
These are notes taken of my continuation of my learning about BINARY SEARCH TREES.
This post has to do with BINARY SEARCH TREES: INSERTION.
If we want to insert 500 to our empty tree, then 500 becomes the root node of the tree.
· If we want to insert 750 to our tree, we always start at the root node.
· We compare 500 to 750 and see which value is greater and if the right child is empty, we insert that value to the right child of the root node.
· If the value we want to insert is less than the root node, and if the left child is empty, we can insert that value to the left child of the root node.
· So, 750 would be inserted to the right side of the root node, since 500 has an empty right child.
· If we want to insert 250 to our tree, we always start at the root node.
· We compare 500 to 250 and see which value is greater and if the right child is empty, we insert that value to the right child of the root node.
· If the value we want to insert is less than the root node, and if the left child is empty, we can insert that value to the left child of the root node.
· Since 250 is less than 500, and if the left child of the root node is empty, we can insert 250 into the left child of the 500 root node.
· If we want to insert 850 to our tree, we always start at the root node.
· Since 850 is greater than 500, then 850 has to be inserted to the right side of the 500 node.
· And since, 500 already as a right child of 750, from the previous example, we advance to the right child of 500.
· Now, we compare 750 to 850 to see which value is greater.
· Since 850 is greater than 750, and since 750 has no right child, then 850 has to be inserted to the right side of the 750 node.
· If we want to insert 350 to our tree, we always start at the root node.
· Since 350 is less than 500, then 350 has to be inserted to the left side of the 500 node.
· And since, 500 already as a left child of 250, from the previous example, we advance to the left child of 500.
· Now, we compare 250 to 350 to see which value is greater.
· Since 350 is greater than 250, and since 250 has no right child, then 350 has to be inserted to the right side of the 250 node.
· If we want to insert 150 to our tree, we always start at the root node.
· Since 150 is less than 500, then 150 has to be inserted to the left side of the 500 node.
· And since, 500 already as a left child of 250, from the previous example, we advance to the left child of 500.
· Now, we compare 250 to 150 to see which value is greater.
· Since 150 is less than 250, and since 250 has no left child, then 150 has to be inserted to the left side of the 250 node.
· If we want to insert 650 to our tree, we always start at the root node.
· Since 650 is greater than 500, then 650 has to be inserted to the right side of the 500 node.
· And since, 500 already as a right child of 750, from the previous example, we advance to the right child of 500.
· Now, we compare 750 to 650 to see which value is greater.
· Since 650 is less than 750, and since 750 has no left child, then 650 has to be inserted to the left side of the 750 node.
BINARY SEARCH TREES: INSERT METHODS
We need two insert methods:
1. node
2. BTS — initial insert call.
class BTS{
insert(data){
if(this.root)
// if there is a root node, then find the root node
// if the tree is empty, skip down to the else statement.
this.root.insert(data);
// if there is a root node, this will look for the root node and will invoke the insert(data) method in class Node.
else
// if the tree is empty, set a new node into this.root
this.root = new Node(data);
// if the tree is empty, set a new node into this.root
}
}
class Node{
insert(data){
if(this.data == data)
// if the data you want to insert is already in the tree, then throw an error
throw new Error(“Data already exist within tree”);
// if the data you want to insert is already in the tree, then throw an error
else if(this.data > data){
// if this.data, which is the data you want to insert, is greater than the data we’re currently at, then do the following (which is to insert data to the left sub-tree, aka left child, of the root node.
// if this.data, which is the data you want to insert, is less than the data we’re currently at, then skip down to the else statement.
if(this.left)
// this is to check to see if there is already data in the left child.
this.left.insert(data);
// if there is data in the left child, then search for an empty left child to insert the data you want to insert.
// if there is data in the left child, then go back up to the “if(this.data == data)” line and continue from there to find an empty child to insert the data you want to insert.
else
// if the left child is empty, then do the following. (which is to insert the data you want to insert)
this.left = new Node(data);
// if the left child is empty, then insert the data you want to insert as a new Node.
}
else {
// from the ‘if statement’ above: if this.data, which is the data you want to insert, is less than the data we’re currently at, then do the following. (which is to insert data to the right sub-tree, aka the right child, of the root node.
if(this.right)
// this is to check to see if there is already data in the right child.
this.right.insert(data);
// if there is data in the right child, then search for an empty right child to insert the data you want to insert.
// if there is data in the right child, then go back up to the “if(this.data == data)” line and continue from there to find an empty child to insert the data you want to insert.
else
// if the right child is empty, then do the following. (which is to insert the data you want to insert)
this.right = new Node(data);
// if the right child is empty, then insert the data you want to insert as a new Node.
}
}
}
I tried to draw out a Binary Search Tree, and it looked good on Microsoft Word but it came out really bad here on Medium, as you can see below.
_______500_______
/ \
__250__ __750_
/ \ / \
150 350 650 850
/ \ / \ / \ / \
100 180 270 400 600 700 830 980
This post covered how to insert numbers into the Binary Search Tree.
I will continue my learning of the Binary Search Trees.
