1.4.2 - Trees and binary search trees

Represent a hierarchy with a rooted tree

A tree connects nodes without cycles. A rooted tree chooses one root and organises the remaining nodes into a hierarchy: every non-root node has exactly one parent. A parent can have several children; a node without children is a leaf. A subtree consists of a node and all its descendants. A root with no children is both the root and a leaf.

In a library hierarchy, Library has children Fiction, Science and History. Fiction has children Novel and Poetry, and Science has child Physics. History is also a leaf. There is exactly one path from the root to each node. Connecting Poetry back to Library would create a cycle, so the result would no longer be this tree. The diagram uses undirected branches; the root gives the parent/child interpretation. An implementation can still store references pointing from parent to child.

[DIAGRAM: General library hierarchy beside a seven-node binary search tree; asset_slug: rooted-tree-and-bst; caption: A general tree can have several children. A binary search tree has at most two and orders their subtrees.]

Creating a general tree starts with a root record and an empty child collection. To add a new leaf, create its record, locate its intended parent and add one link from that parent. Reject a link to an ancestor because it would create a cycle; attaching an already attached node to another parent also breaks the one-parent rule. Removing a leaf removes its parent's link, then releases the record or lets garbage collection reclaim it. Removing the only root leaves an empty tree.

Removing an internal node needs a stated policy. A folder deletion could remove its whole subtree. Alternatively, an organisation might promote its children to the deleted node's parent; that changes their level and meaning. These are different contracts, not automatic consequences of the word delete. A general tree has no key-order rule, so finding a name may require traversing every node and comparing it. Each recursive visit processes the current node then visits its children; an empty tree has nothing to visit.

Store two links and preserve the search ordering

A binary tree has at most two children per node, distinguished as left and right.

For root 40 with children 20 and 60, node 35 can occur in 20's right subtree because it is greater than 20 and smaller than 40. Node 45 cannot occur anywhere in 40's left subtree, even if it is the right child of 20. A separate duplicate-key policy is essential: here an existing key is retained and a repeated insertion does nothing. Other applications could store a count or collection of records at that key.

An array of records can model the links using indices. NULL is a sentinel for no link, never a valid occupied index. In the table, root = 0; physical array order does not determine traversal order.

Creation reserves storage, marks slots unused and sets root = NULL. The first insertion obtains a free slot and changes root. Later insertion obtains a free slot and changes an existing node's left or right index. Removal returns its slot to a free-storage list; do not shift occupied records and leave their old indices pointing to the wrong nodes. Fixed capacity can be exhausted even when the logical operation is valid.

An object representation instead stores a key and two references in each node. Creation allocates objects as needed rather than reserving all slots. Either approach represents the same logical tree. This Python dictionary is a small record representation; None means no child:

def node(key):
    return {"key": key, "left": None, "right": None}

root = node(40)
root["left"] = node(20)
root["right"] = node(60)

Create, find and insert by following comparisons

Searching a BST eliminates a whole subtree at each unequal comparison. Start at the root. Equality means found; a smaller target takes the left link; a larger target takes the right link. Reaching an absent link means not found, not a value of zero. Searching for 50 in the table visits 40, 60, 50. Searching for 55 visits those same keys then follows 50's absent right link and returns false.

This static Python example represents nodes with the records defined above. It assumes a finite valid BST and comparable integer keys. It illustrates the algorithm; prediction questions do not have Run.

def contains(root, target):
    current = root
    while current is not None:
        if target == current["key"]:
            return True
        if target < current["key"]:
            current = current["left"]
        else:
            current = current["right"]
    return False

def insert(root, key):
    if root is None:
        return node(key)
    current = root
    while True:
        if key == current["key"]:
            return root
        side = "left" if key < current["key"] else "right"
        if current[side] is None:
            current[side] = node(key)
            return root
        current = current[side]

root = None
for key in [40, 20, 60, 10, 30, 50, 70]:
    root = insert(root, key)

Insertion follows the same comparisons as search but uses the first absent link to attach a new leaf. Inserting 25 visits 40, 20, 30, then creates 25 as 30's left child. Existing branches are retained. The caller writes root = insert(root, key) because inserting into an empty tree changes the root reference; inserting into a non-empty one returns the same root object. A duplicate returns without allocation. A search for any value in an empty tree immediately returns false.

There is no loop that scans the array indices in order: the logical child links select the next record. Each iteration descends one level, so a valid finite tree eventually reaches equality or an absent link. Malformed cycles and missing record fields are outside this small routine's contract and should be prevented by construction rather than silently treated as search misses.

Experiment with insertion and lookup

This ungraded sandbox starts fresh and includes its own definitions. Predict the sorted keys and two lookup results, then run. Changing the data lets you test the duplicate and empty-tree policies without changing the algorithm.