CODE EXAMPLE FOR JAVA

Binary Search Tree

"""Binary Search Tree

Included:
	- Insert
    - Find data/ minimum/ maximum
    - Size
    - Height
    - Traversals (Inorder, preorder, postorder)
    - Test Code for it
    
Not included:
	- Delete
    - Display (as 2D BST)
	and others...
"""

class Node: # Node
    def __init__(self, data, start=None):
        self.data = data
        self.left = self.right = start

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # Insert a node
    def put(self, data):
        if self.root is None: # BST empty
            self.root = Node(data)
        else:
            curr = self.root # initialise curr pointer
            while curr:
                if data < curr.data: # data put at left
                    if curr.left:
                        curr = curr.left
                    else: # no left child
                        curr.left = Node(data)
                        break
                else: # data put at right
                    if curr.right:
                        curr = curr.right
                    else:  # no right child
                        curr.right = Node(data)
                        break   
                        
    def find(self, data):
        curr = self.root   # start from root
        while curr:
            if data < curr.data:  # data at left
                curr = curr.left
            elif data > curr.data:    # data at right
                curr = curr.right
            else:
                return True # found
        return False
    
    def min_of(self):
        curr = self.root # start from root
        while curr.left:
            curr = curr.left # keep going left
        return curr.data
        
    def max_of(self):
        curr = self.root # start from root
        while curr.right:
            curr = curr.right # keep going right
        return curr.data
    
    def size(self):
        def go(node): # helper
            if node:
                return 1 + go(node.left) + go(node.right)
            return 0
        return go(self.root)   
    
    def height(self):
        def go(node): # helper
            if node:
                return 1 + max(go(node.left), go(node.right))
            return -1 # it has -1 if empty
        return go(self.root)

        
    # In_order
    def in_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                go(node.left) # left
                lst.append(node.data) # Node
                go(node.right) # Right
        go(self.root)
        return lst
    
    # Pre_order
    def pre_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                lst.append(node.data) # Node
                go(node.left) # left
                go(node.right) # Right
        go(self.root)
        return lst
    
    # Post_order
    def post_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                go(node.left) # left
                go(node.right) # Right
                lst.append(node.data) # Node
        go(self.root)
        return lst

# Test
from random import randint, sample
def BST_tester(BST):
    r = randint(5, 10)
    lst = [randint(10, 100) for _ in range(r)]
    print(f"List: {lst}", 
          f"Sorted: {sorted(lst)}",
          sep = "
", end = "

")
    
    B = BST()
    for item in lst:
        B.put(item)
    lst.sort()
    print("AFTER INSERTION:",
          f"Size: {B.size()} | {B.size() == len(lst)}",
          f"Height: {B.height()} | I can't code the display for this",
          f"Min: {B.min_()} | {B.min_() == min(lst)}",
          f"Max: {B.max_()} | {B.max_() == max(lst)}",
          sep = "
", end = "

")
    
    items = sample(lst, 5) + [randint(10, 100) for _ in range(5)] # 5 confirm in list, 5 might be in list
    found = [B.find(_) for _ in items]
    zipped = list(zip(items, found))
    inlst, notinlst = zipped[:5], zipped[5:] 
    print(f"Sampled from lst: {inlst} | All True: {all(found[:5])}",
          f"Random: {notinlst}",
          sep = "
", end = "

")
    
    print(f"Inord: {B.in_ord()} | Correct Insertion: {lst == B.in_ord()}",
          f"Preord: {B.pre_ord()}",
          f"Postord: {B.post_ord()}",
          sep = "
")
BST_tester(BST)