Trees, binary search trees, binary heaps

Tree terminology

Definition. A tree is a connected acyclic graph, often represented with a root and parent-child relations. The root has no parent; a leaf has no children. Depth counts edges from the root, while height counts the longest downward edge path to a leaf; an empty-tree height convention must be stated.

Example. In a rooted tree A→{B,C}, A is parent and B,C are children.

Exam point. Some definitions count nodes rather than edges for height; use the stated convention.

Binary trees

Definition. A binary tree has at most two children per node, distinguished as left and right. A full binary tree has either zero or two children at every node; a complete binary tree fills levels left to right with only the last level possibly incomplete. A perfect binary tree is both full and has every leaf at the same depth.

Example. A complete tree with six nodes has level-order positions 1 through 6 filled.

Exam point. Full, complete, and perfect are distinct properties.

Binary-tree properties

Definition. At depth d, a binary tree has at most $2^d$ nodes. A perfect binary tree of height h measured in edges has $2^{h+1}-1$ nodes. A complete binary tree with n nodes has height $\lfloor\log_2 n\rfloor$ under edge-count height for n≥1.

Example. A perfect tree of height 2 has 7 nodes.

Exam point. Check whether height is counted in edges or levels.

Solved calculation. A perfect binary tree has 31 nodes. Find its height in edges and number of leaves.

1. $2^{h+1}-1=31$ gives $2^{h+1}=32=2^5$.
2. Therefore $h=4$.
3. A perfect binary tree has $2^h=16$ leaves. Answer. Height 4 edges, 16 leaves.

Tree representations

Definition. Linked representation stores a node with data and child pointers. Array representation is natural for complete trees: with zero-based indices, left child of i is $2i+1$, right child is $2i+2$, and parent is $\lfloor(i-1)/2\rfloor$ for i>0. Sparse trees can waste array positions.

Example. At index 2, left child index is 5 and right child is 6.

Exam point. Do not use one-based formulas in a zero-based array.

Solved calculation. In a zero-based tree array, node index 11 has which parent and children indices?

1. Parent index is $\lfloor(11-1)/2\rfloor=5$.
2. Left child is $2(11)+1=23$.
3. Right child is $2(11)+2=24$. Answer. Parent 5; children 23 and 24, if those array positions are occupied.

Tree traversals

Definition. Preorder visits root, left subtree, right subtree. Inorder visits left subtree, root, right subtree. Postorder visits left subtree, right subtree, root. Level-order visits nodes breadth-first, usually using a queue.

Example. For root A with children B and C, inorder is B,A,C.

Exam point. Inorder yields sorted order only for a binary search tree.

Solved trace. For the tree A with left child B and right child C; B has right child D; C has left child E, list traversals.

1. Preorder: A, then B,D, then C,E → A,B,D,C,E.
2. Inorder: B,D, then A, then E,C → B,D,A,E,C.
3. Postorder: D,B, E,C, then A → D,B,E,C,A.
4. Level-order: A, then B,C, then D,E → A,B,C,D,E. Answer. Preorder A,B,D,C,E; inorder B,D,A,E,C; postorder D,B,E,C,A; level-order A,B,C,D,E.

Binary search tree property

Definition. A binary search tree (BST) orders keys so that every key in the left subtree is less than the node key and every key in the right subtree is greater, under the chosen duplicate-key policy. The property applies recursively to entire subtrees, not just immediate children.

Example. Root 8 may have left child 3 and right child 12; all keys below 3 must remain less than 8.

Exam point. A node can violate the BST rule because of an ancestor bound even if it compares correctly with its parent.

BST search

Definition. Search compares the target with the current node and continues left or right. At each step, an entire subtree is discarded. Search time is O(h), where h is tree height; it is O(log n) for a balanced tree and O(n) in a degenerate chain.

Example. Searching 11 at root 8 goes right before any lower comparison.

Exam point. BSTs do not automatically remain balanced.

Solved trace. Search key 14 in BST root 20, left child 9 (children 4 and 13; 13 has right child 17), and right child 30.

1. Compare 14 with 20; go left.
2. Compare 14 with 9; go right to 13.
3. Compare 14 with 13; go right to 17.
4. Compare 14 with 17; go left to NULL. Answer. Not found after four key comparisons.

BST insertion

Definition. Insert follows the search path until reaching a null child and places a new leaf there. With distinct keys, insertion preserves the BST ordering property. Its time is O(h); inserting sorted values into an unbalanced ordinary BST can create height n−1.

Example. Inserting 6 into a tree where 6 belongs between 5 and 8 attaches it as the appropriate null child.

Exam point. Insertion order affects the shape of an ordinary BST.

Solved construction. Insert 8, 3, 10, 1, 6, 14, 4 into an empty BST. Show the final tree.

1. 8 becomes root.
2. 3 goes left of 8; 10 goes right.
3. 1 goes left of 3; 6 goes right of 3.
4. 14 goes right of 10; 4 goes left of 6.

        8
      /   \
     3     10
    / \      \
   1   6      14
      /
     4

Answer. The displayed BST is the final structure.

BST deletion cases

Definition. Deleting a leaf removes it directly. Deleting a node with one child links its parent to that child. Deleting a node with two children replaces its key with its inorder successor (minimum in right subtree) or predecessor (maximum in left subtree), then deletes that replacement node from its former position.

Example. The inorder successor of 8 is the smallest key greater than 8.

Exam point. After replacement, remove the successor's old node; do not duplicate it.

Solved deletion. Delete key 8 from the BST formed by insertion 8,3,10,1,6,14,4 above, using the inorder successor.

1. Node 8 has two children.
2. Its right subtree contains 10 and 14; the minimum is 10.
3. Replace key 8 with 10.
4. Delete the original 10 node; it has one right child 14, which takes its place.
5. New root is 10, with left subtree rooted at 3 and right child 14. Answer. Root 10; left subtree unchanged; right child 14.