6 Trees and Binary Search Trees

Learn how trees are structured, traversed, analyzed recursively, and used as binary search trees for efficient searching, insertion, and deletion.

structure and terminology

A represents hierarchical information with nodes and edges. It begins at a distinguished root, and each node may have zero or more children. A node with no children is a leaf. Because a has no cycles, there is exactly one path from the root to every reachable node.

Common terminology includes:

A parent is directly above a node, and a child is directly below its parent.
Siblings share the same parent.
An internal node has at least one child.
An ancestor lies on the path from the root to another node; a descendant lies below another node.
A subtree consists of a node together with all of its descendants.
The depth of a node is its number of edges from the root.
The degree of a node is its number of children.
The of a node is the number of edges on its longest downward path to a leaf.

If a contains $n$ nodes, an algorithm that processes every node has time complexity $O(n)$ . An empty- convention may use $-1$ or $0$ , but an implementation must use one convention consistently.

Takeaway: Trees organize data hierarchically; depth measures distance downward from the root, while measures the longest path downward from a node.

shapes

A has at most two children per node: a left child and a right child. It is either empty or consists of a root, a left binary subtree, and a right binary subtree.

Important forms include:

A full gives every node either zero children or exactly two children.
A complete fills every level except possibly the last, with the final level filled from left to right.
A perfect has two children at every internal node, and all leaves have the same depth.
A keeps subtree heights sufficiently similar.
A degenerate gives each node only one child, making the structure behave like a linked list.

For a perfect of $h$ , the number of nodes is

1+2+4+\cdots+2^h=2^{h+1}-1.

Therefore, a can contain exponentially many nodes relative to its . A balanced with $n$ nodes has approximately $\log_2 n$ , whereas a highly skewed can have $n-1$ .

Takeaway: The shape of a determines how much work a path-based algorithm may require.

Visiting nodes in different orders

A visits nodes in a defined order. The four standard orders are depth-first preorder, inorder, and postorder, plus breadth-first level-order.

Preorder uses node, left subtree, right subtree. It is useful for copying a , producing a prefix expression, or recording a structure before its descendants.
uses left subtree, node, right subtree. In a , it visits keys in sorted order.
Postorder uses left subtree, right subtree, node. It is useful when children must be processed before their parent, such as deleting a or evaluating a postfix expression.
Level-order traversal visits nodes by depth, beginning with the root. It is equivalent to breadth-first search from the root and typically uses a queue.

For the with root A, children B and C, and lower-level nodes D, E, and F, the orders are:

Preorder: A, B, D, E, C, F
Inorder: D, B, E, A, C, F
Postorder: D, E, B, F, C, A
Level-order: A, B, C, D, E, F

Every standard traversal visits each node once, so its time complexity is $O(n)$ . Recursive depth-first traversals use $O(h)$ auxiliary space, where $h$ is . Level-order traversal uses $O(w)$ space, where $w$ is the maximum width of a level.

Takeaway: Choose the traversal order according to when each node should be processed relative to its children.

Recursive algorithms on trees

Trees naturally support recursive algorithms because each child is the root of a smaller subtree. A typical recursive algorithm has an empty-subtree base case, recursive calls on child subtrees, and a combination step.

To count nodes, return zero for an empty subtree. Otherwise, return one for the current node plus the counts of the left and right subtrees. Each node is visited once, so the running time is $O(n)$ , and the recursion stack uses $O(h)$ space.

To compute using the empty- convention $-1$ , return $-1$ for an empty subtree. Otherwise, compute both child heights and return

1+\max(\text{left height},\text{right height}).

This also takes $O(n)$ time because every node must be examined.

Searching an ordinary is different from searching a . Without an ordering property, the target may be anywhere, so an algorithm may need to inspect both subtrees. Its worst-case time complexity is $O(n)$ .

Takeaway: Recursion divides a problem into smaller subtree problems, but it does not by itself make an unordered search fast.

The invariant

A adds an ordering invariant to a . For each node, every key in the left subtree is less than the node's key, and every key in the right subtree is greater:

\text{left keys}<\text{node key}<\text{right keys}.

If duplicates are allowed, the implementation must choose a consistent rule, such as placing duplicates on one side or storing a count in the node.

During search, compare the target with the current key. If they are equal, the search succeeds. If the target is smaller, continue in the left subtree; otherwise, continue in the right subtree. Only one root-to-leaf path is followed, so the running time is $O(h)$ , where $h$ is the .

Insertion uses the same comparisons until it finds an empty child position. It then creates the new node there. Insertion also takes $O(h)$ time and $O(h)$ recursive stack space.

is a key consequence of the ordering invariant: it lists all keys in sorted order. This makes it useful for producing an ordered view of the stored data.

Takeaway: The ordering rule lets search and insertion discard an entire subtree at each comparison.

BST updates and complexity

BST deletion has three structural cases:

A leaf has no children, so it can be removed directly.
A node with one child is replaced by that child.
A node with two children is replaced by its , the smallest key in its right subtree, or alternatively by its inorder predecessor. The replacement node is then deleted from its original position.

To find the minimum key in a nonempty subtree, start at its root and repeatedly follow left-child links until no left child remains. The same path-based reasoning gives deletion time complexity $O(h)$ .

The main operations therefore have these bounds:

In a balanced BST, search, insertion, deletion, and finding a minimum or maximum take $O(\log n)$ .
In a skewed BST, the same operations can take $O(n)$ .
takes $O(n)$ regardless of whether the is balanced.
Recursive operation space is $O(\log n)$ for a balanced and $O(n)$ for a maximally skewed .

Inserting already sorted values such as 1, 2, 3, 4, 5 can create a one-sided chain. Ordinary BSTs do not balance themselves automatically; AVL trees and red-black trees add restructuring rules to keep $O(\log n)$ .

Takeaway: BST efficiency depends on . The ordering property helps only when the shape keeps root-to-leaf paths short.

Tree structure and terminology

Binary tree shapes