Trees and Binary Search Trees

An undirected tree is connected and has no cycles. A tree does not inherently require a chosen root. Choosing a root gives every other vertex a parent on the unique route towards it, creating a hierarchy of ancestors and descendants. A leaf has no children in that rooted interpretation.

A binary tree is rooted and allows at most two children per node. It need not be full, complete or ordered. A node with only one child is permitted, so “binary” does not mean every node must have exactly two children.

In a binary search tree with distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. This rule applies to whole subtrees, not only immediate children. A duplicate-key policy must be specified separately if duplicates are allowed.

Insertion compares a new key at successive nodes and follows the relevant branch until an empty child position is found. A search can discard an entire subtree after each comparison because the invariant rules out the target there. Arbitrary binary trees do not provide this guarantee.

A reasonably balanced search tree has height proportional to log V, making its search path short. Inserting already sorted distinct keys into an ordinary unbalanced tree can produce a chain with height proportional to V, and search then becomes linear.

Tree structure affects algorithms and storage decisions. An expression tree represents operators and operands; a directory tree represents containment. The binary-search ordering rule is useful only when it fits the application. A diagram should identify the root, child ordering and any key policy before a trace begins.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.