Quartz 5

BST REVISION

2 min read

BST REVISION

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
    def __str__(self):
        string = f"Node({self.data}, "
        if self.left:
            string += f"{self.left.data}, "
        else:
            string += f"{self.left}, "
 
        if self.right:
            string += f"{self.right.data})"
        else:
            string += f"{self.right})"
 
        return string
l = Node(5)
r = Node(15)
n1 = Node(10, l, r)
 
l2 = Node(1)
r2 = Node(3)
n2 = Node(n1, l2, r2)
print(n1)
print(n1.left)
 
print(n2)

Output:

Node(10, 5, 15)
Node(5, None, None)
Node(Node(10, 5, 15), 1, 3)
class BinarySearchTree():
    def __init__(self):
        self.root = None
 
    def add(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self.add2(self.root, data)
    
    def add2(self, root, data):
        if data < root.data:
            if root.left is None:
                root.left = Node(data)
            else:
                self.add2(root.left, data) 
                # this starts the recursion. it tries to go one level deeper and find a suitable location where the node is empty. 
        else:
            if root.right is None:
                root.right = Node(data)
            else:
                self.add2(root.right, data)
 
    def inorder(self, root):
        if root != None:
            self.inorder(root.left)
            print(root.data)
            self.inorder(root.right)
 
    def preorder(self, root):
        if root != None:
            print(root.data)
            self.preorder(root.left)
            self.preorder(root.right)
 
    def postorder(self, root):
        if root != None:
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.data)
    
    def reverseInOrder(self, root):
        if root != None:
            self.reverseInOrder(root.right)
            print(root.data)
            self.reverseInOrder(root.left)
 
    def find(self, item, tree):
        if tree == None:
            return False
        elif item < tree.data:
            return self.find(item, tree.left)
        elif item > tree.data:
            return self.find(item, tree.right)
        else:
            return tree
        
    def count(self, tree):
        if tree == None:
            return 0
        else:
            return self.count(tree.left) + self.count(tree.right) + 1
t = BinarySearchTree()
t.add(5)
t.add(10)
t.add(2)
t.add(1)
t.add(15)
 
print("Root:", t.root)
print("\nIn order:")
t.inorder(t.root)
 
 
print(f"\nCount: {t.count(t.root)}")
node = t.find(0, t.root)
print(f"Find '0' results: {node}")
 
t.add(13)
print('\nAdded 13 print in order:')
t.inorder(t.root)
 
print('\nPostorder:')
t.postorder(t.root)
 
print('\nPreorder:')
t.preorder(t.root)
 
print('\nReverseInOrder:')
t.reverseInOrder(t.root)

Output:

Root: Node(5, 2, 10)
 
In order:
1
2
5
10
15
 
Count: 5
Find '0' results: False
 
Added 13 print in order:
1
2
5
10
13
15
 
Postorder:
1
2
13
15
10
5
 
Preorder:
5
2
1
10
15
13
 
ReverseInOrder:
15
13
10
5
2
1

Graph View