Hello! Finally, I am free from the shackles of university. I have all the time in the world to work on some side projects. Lately, I have been trying to learn whatever stuff I am interested in. I've been planning on going over some concepts in computer science that just went past me during my 4 year journey.
One of which are Binary Search Trees.
A Binary Search Tree stores data in a manner that is like a tree, hence the name. Each data in the tree is called a node. A node can only have two descendants, one on the left and one on the right.
It pretty much looks like this. (Thanks, Wikipedia!)
Data in the tree is already sorted. It is because of its simple but effective rules on how data goes into the tree.
- All nodes of left subtree are less than root node
- All nodes of right subtree are more than root node
The root node (the 8 in the picture above!) has descendants that are also Binary Search Trees, which mean that the two rules also apply to them.
Another thing to note is that if a node does not have any descendant, it's called a leaf node.
Read more about it here.
On to my implementation then. I tried to make it as simple and clean as I could. Copy paste it to your editor of choice and run it through Python 3.
class Node:
key = None
leftNode = None
rightNode = None
def __init__(self, key):
self.key = key
def getLeftNode(self):
return self.leftNode
def setLeftNode(self, node):
self.leftNode = node
def getRightNode(self):
return self.rightNode
def setRightNode(self, node):
self.rightNode = node
def printAllNodes(rootNode):
node = rootNode
print(f"Current Node: {node.key} -> ", end='')
if (node.leftNode != None):
print(f"Left Node: {node.getLeftNode().key} -> ",end='')
printAllNodes(node.leftNode)
else:
print("Left Node: Empty -> ",end='')
if (node.rightNode != None):
print(f"Right Node: {node.getRightNode().key} -> ", end='')
printAllNodes(node.rightNode)
else:
print("Right Node: Empty")
if (node.leftNode == None and node.rightNode == None):
print(f"Current Node {node.key} is a leaf!")
def addNode(currentNode, newNode):
if (newNode.key < currentNode.key):
if (currentNode.leftNode != None):
addNode(currentNode.leftNode, newNode)
else:
currentNode.setLeftNode(newNode)
elif (newNode.key > currentNode.key):
if (currentNode.rightNode != None):
addNode(currentNode.rightNode, newNode)
else:
currentNode.setRightNode(newNode)
else:
return False
def searchNode(currentNode, node):
if (node.key == currentNode.key):
return True
elif (node.key < currentNode.key):
if (currentNode.leftNode != None):
if (searchNode(currentNode.leftNode, node)):
return (True)
else:
return False
elif (node.key > currentNode.key):
if (currentNode.rightNode != None):
if (searchNode(currentNode.rightNode, node)):
return (True)
else:
return False
def main():
rootNode = Node(7)
addNode(rootNode, Node(4))
addNode(rootNode, Node(8))
addNode(rootNode, Node(10))
addNode(rootNode, Node(3))
addNode(rootNode, Node(69))
printAllNodes(rootNode)
testNode = Node(10)
if (searchNode(rootNode, testNode)):
print(f"Node with key {testNode.key} was found!")
else:
print(f"Node with key {testNode.key} was not found in tree.")
main()