Lessons · Python · binary trees
A node, a left and a right
A binary tree node holds a value and at most two children. In a binary SEARCH tree, everything left of a node is smaller and everything right is larger.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
That one ordering rule lets a search discard half the remaining tree at every step, which is the same bargain binary search makes on a sorted list, and it is why sorted maps and database indexes are shaped like this.
How to think about it
Almost every tree function is three lines of thought: what is the answer for an empty tree (None), what is the answer for this node, and what do I ask of the left and right children. Write those three and the recursion falls out.
Worked example
class Node:Value, left, right.
def __init__(self, value, left=None, right=None):Both children default to nothing.
self.value, self.left, self.right = value, left, right
root = Node(5, Node(3, Node(1), Node(4)), Node(8))Left of 5 is smaller; right is larger.
def find(node, wanted):The search.
if node is None: return FalseEmpty tree: not here.
if node.value == wanted: return TrueThis node.
if wanted < node.value: return find(node.left, wanted)Smaller: the whole right side is discarded.
return find(node.right, wanted)Larger: the left side is discarded.
print(find(root, 4), find(root, 7))True False
def height(node):How deep it goes.
return 0 if node is None else 1 + max(height(node.left), height(node.right))The three lines of thought again.
print(height(root))3
Your turn
Take the branch that can still hold the value.
if wanted < node.value:
return find(node., wanted)Solve one with the tests running
The trap
The log-n speed depends on the tree being balanced. Insert 1, 2, 3, 4, 5 in order and every node has only a right child: a linked list with extra steps, and every search is back to n.