Binary Search Trees!

5 years ago July 30, 2019 - 12:07 pm

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()