Programming

  minte9
LearnRemember



Data Structures / Binary Search Trees 

What is a tree?
What is a binary tree?
What is a binary search tree (BST)?
What are the constrains for descendants in a BST?

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




References