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:
return node
if value < node.value:
return search(value, node.leftChild)
if value > node.value:
return search(value, node.rightChild)
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))
node3 = Tree(75, node6, node7)
node2 = Tree(25, node4, node5)
node1 = Tree(50, node2, node3)
node = search(61, node1)
print(node.value)
