minte9

LearnRemember / ALGORITHMS

Binary Tree

In a tree, each node have links to multiple nodes. A binary tree is a tree in which each node has zero, one, or two children.

Binary Search Tree (BST)

The left node can contains descendants that are less than the node itself. Likewise, the right node has descendants greater than the node.

 
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.leftChild = left
        self.rightChild = right
    
node1 = Tree(25)
node2 = Tree(75)
root = Tree(50, node1, node2)

assert root.value > root.leftChild.value
assert root.value < root.rightChild.value

Search Node

Recursion is key when dealing with data structures with arbitrary number of levels.

 
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.leftChild = left
        self.rightChild = right

def search(value, node):
    if value == node.value: # Base Case
        return node

    if value < node.value:
        return search(value, node.leftChild)

    if value > node.value:
        return search(value, node.rightChild)

# Level 2
node7 = Tree(89, Tree(82), Tree(95))
node6 = Tree(56, Tree(52), Tree(61))
node5 = Tree(33, Tree(30), Tree(40))
node4 = Tree(10, Tree(4), Tree(11))

# Level 1
node3 = Tree(75, node6, node7)
node2 = Tree(25, node4, node5)

# Level 0 - root
node1 = Tree(50, node2, node3)

# Searching
node = search(61, node1)
print(node.value) # 61