Binary search trees and traversals

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right


def height(node):
    return 1


root = Node(50, Node(30, Node(20), Node(40, Node(35))), Node(70))
print(height(root))

Deleting a node: three cases

Removing a value has to keep the search-tree rule true. Find the node first, then:

1. No children (a leaf): just remove it.
2. One child: let that child take the node's place.
3. Two children: the node's value has to be replaced by one that still sits between its left and right sides. The smallest value in its right subtree (its in-order successor) works: copy that value up, then delete it from the right subtree, where it has at most one child, so it's case 1 or 2.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def in_order(n):
    return [] if n is None else in_order(n.left) + [n.key] + in_order(n.right)

def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right          # cases 1 and 2
        if node.right is None:
            return node.left
        successor = node.right         # case 3: the smallest key on the right
        while successor.left:
            successor = successor.left
        node.key = successor.key
        node.right = delete(node.right, successor.key)
    return node

root = Node(50, Node(30, Node(20), Node(40)), Node(70, Node(60), Node(80)))
root = delete(root, 20)   # a leaf
root = delete(root, 30)   # now has one child, 40
root = delete(root, 50)   # two children: 60 takes its place
print(root.key, in_order(root))

When the tree is lopsided

The fast search depends on the tree being bushy. Insert values that are already sorted and every new node goes to the right of the last one: the "tree" is a chain, and searching it means walking every node, like a list.

import random

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert(root, key):
    if root is None:
        return Node(key)
    node = root
    while True:  # a loop, so a long chain can't overflow the call stack
        side = "left" if key < node.key else "right"
        child = getattr(node, side)
        if child is None:
            setattr(node, side, Node(key))
            return root
        node = child

def height(node):
    return 0 if node is None else 1 + max(height(node.left), height(node.right))

keys = list(range(400))
shuffled = random.Random(5).sample(keys, len(keys))
for name, order in [("sorted order", keys), ("random order", shuffled)]:
    root = None
    for k in order:
        root = insert(root, k)
    print(f"{name}: height {height(root)} for {len(order)} keys")

A height of 400 means 400 steps to find the last key; a random order gives around 20. Balanced trees, with names like AVL and red-black trees, fix this by rotating nodes during each insert so the height stays close to log₂ n whatever the order. You'll rarely write one, but they're behind sorted maps in many languages.

Databases go a step further. A B-tree node holds hundreds of keys instead of one, so even a table of a billion rows needs only three or four levels, and each level is one read from disk. That's what CREATE INDEX builds in the SQL lesson, and why a lookup by an indexed column stays fast as the table grows. In everyday Python, reach for a dict or set (hash tables) for lookups, and a sorted list with the bisect module when you need order.

Trees you already use

Binary search trees are one kind of a shape you meet everywhere in software, so the four walks pay off far beyond interviews:

• Folders and files are a tree. Adding up a folder's size is a post-order walk, and os.walk hands you the folders from the top down, like pre-order.
• A web page is a tree of elements, the DOM. When you scraped the practice shop with Beautiful Soup, find_all was walking that tree for you.
• JSON from an API is a tree of dictionaries and lists, which is why nested data needs a recursive function to search it.
• Code itself becomes a tree before Python runs it, a syntax tree, and tools like linters and formatters walk it.
• Decision trees, in the machine-learning phase, are binary trees whose nodes ask questions about the data.

The habit to take away is the question you ask before writing any tree code: does each node need its children's answers first (post-order), or does it pass something down to them (pre-order, like the bounds in the next example)?

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def looks_valid(node):
    """The tempting version: only checks each node against its own children."""
    if node is None:
        return True
    if node.left and node.left.key >= node.key:
        return False
    if node.right and node.right.key <= node.key:
        return False
    return looks_valid(node.left) and looks_valid(node.right)

def is_valid(node, low=float("-inf"), high=float("inf")):
    """Every key must fit between the bounds its ancestors set."""
    if node is None:
        return True
    if not (low < node.key < high):
        return False
    return is_valid(node.left, low, node.key) and is_valid(node.right, node.key, high)

tricky = Node(50, Node(30, None, Node(60)), Node(70))  # 60 is right of 30 but left of 50
print(looks_valid(tricky), is_valid(tricky))