hi, this is part 4 of the tree data structure we'll explain binary search tree operations with their implementation such as insertion, and search.
In the next post, we will talk about the deletion.
#day_16
Insertion in the binary search tree
- Let's say we want to insert 17 in this binary search tree.
20
/ \
12 23
/ \ / \
7 15 21 35
- Since 17 < 20, we will go to the left sub-tree.
- 17 > 12, we will go the right.
- 17 > 15 and the no more child in the right's why we will go to the right and insert it. so this binary search tree above will be like this:
20
/ \
12 23
/ \ / \
7 15 21 35
\
17
The insert approach
- We need to know that the inserted node will be always one of the binary search tree leaves.
- while the root is None(null) store the previous root in a variable
- if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree
root = root. right
- else (that means the previousRoot is greater than or equal the elementToInsert) move to the root of the left sub-tree
root = root. left
- if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree
- When the loop break (stop), the previous root will be:
- case 1:
previousRoot = None
if the binary search tree is empty. so the previousRoot will be the new NodepreviousRoot = Node(elementToInsert)
- case 2:
previousRoot < elementToInsert
if the previousRoot is less than the elementToInsert, so the node will be the right child of the previousRootpreviousRoot.right = elementToInsert
- case 3:
previousRoot >= elementToInsert
if the previousRoot is greater than or equal the elementToInsert, so the node will be the left child of the previousRootpreviousRoot.left = elementToInsert
- case 1:
Implementation of insert using python
def insert(elementToInsert: int, root = None):
# new node
TheNewNode = Node(elementToInsert)
previousRoot = None
while root is not None:
previousRoot = root
# if the root's value is less than elementToInsert
if root.value < elementToInsert:
# the root variable will be the root of the right sub-tree
root = root.right
# if the root value is greater than or equal elementToInsert
else:
# the root variable will be the root of the left sub-tree
root = root.left
# if the binary search tree is empty
if previousRoot is None:
previousRoot = TheNewNode
# if the previous root value is greater than or equal the elementToInsert
elif previousRoot.value >= elementToInsert:
# the new node will be its left child
previousRoot.left = TheNewNode
# if the previous root value is less than the elementToInsert
else:
# the new node will be its right child
previousRoot.right = TheNewNode
return TheNewNode
Search in the binary search tree
We want to search for example the number 21
20
/ \
12 23
/ \ / \
7 15 21 35
- start from the root and compare its value with the wanted number (20 < 21), so we will go to the right sub-tree and compare its root with the wanted element.
- (23 > 21), that's why we will go to the left sub-tree and compare its root with the wanted element.
- since (21 == 21), will return the node
the search approach
- compare the root value with the wanted element.
- If the root is None (null) that means the element is not found return False.
- Else If the root is equal to the wanted element return the root.
- Else If the root is greater than it, return the same function with these arguments:(root of the left sub-tree, wanted element)
- Else (that means the root is less than the wanted element) return the same function with these arguments:(root of the right sub-tree, wanted element)
implementation of the search algorithm in the binary search tree
# If there are no more nodes.
# that means the node value will be None(null)
# that means the wanted element doesn't exist
if root == None:
# the wanted element is not found so return False
return False
# if the root value is equal to the wanted element
# that means the wanted element is found
if root.value == wantedElement:
# return the node
return root
# if the root value is smaller than the wanted element
if root.value < wantedElement:
# return the same function with the root of the right sub-tree
return search( wantedElement, root.right)
# if the root value is greater than or equal the wanted element
if root.value >= wantedElement:
# return the same function with the root of the left sub-tree
return search( wantedElement, root.left)
Happy coding! see you next post (we will discuss deletion)
Top comments (0)