Binary Trees & BSTs

Lesson 5 · OKSTEM College · AS Computer Science

Binary Search Tree Property

In a BST: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This enables binary search on a dynamic set.

class BSTNode: def __init__(self, val): self.val=val; self.left=self.right=None class BST: def __init__(self): self.root=None def insert(self, val): def _ins(node, v): if not node: return BSTNode(v) if v < node.val: node.left=_ins(node.left, v) elif v > node.val: node.right=_ins(node.right, v) return node self.root=_ins(self.root, val) def inorder(self): # yields sorted values def _io(node): if node: yield from _io(node.left); yield node.val; yield from _io(node.right) return list(_io(self.root))

BST Complexity

Operation	Balanced BST	Degenerate BST
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

A BST degenerates to a linked list if items are inserted in sorted order. Self-balancing trees (AVL, Red-Black) guarantee O(log n) by rotating after insertions.

BST Deletion — Three Cases

Leaf node: simply remove it.

One child: replace node with its child.

Two children: replace node’s value with its in-order successor (smallest in right subtree), then delete the successor.

Practice

1. What is the inorder traversal of a BST containing 5, 3, 7, 1, 4?

Inorder (L-Root-R) of a BST always yields sorted order: 1, 3, 4, 5, 7

2. How does AVL tree self-balance after insertion?

After each insert, AVL checks the balance factor (height_left - height_right) at every ancestor. If any node has |balance| > 1, it performs one of four rotations (LL, RR, LR, RL) to restore balance. Guarantees O(log n) height.

Knowledge Check

BST inorder traversal always yields

Correct — BST property ensures left < root < right at every node; inorder follows this.

Insertion order is not preserved; BST reorganises by value.

BST traversal is deterministic.

That would be reverse-inorder (right, root, left).

Recap: BST + inorder = sorted output. This is why sorting via BST insertion is O(n log n) — equivalent to tree sort.

Worst-case BST search is O(n) when

Balanced BST search is O(log n).

Correct — sorted insertion builds a degenerate BST (like a linked list).

Duplicates cause issues but don't necessarily make search O(n).

One large root doesn't cause O(n) — the overall structure matters.

Recap: insert 1, 2, 3, 4, 5 in order → each goes to the right child → linked list. O(n) search. Solution: self-balancing trees.

Deleting a node with two children in a BST requires

That would lose all children's data.

Correct — inorder successor is the smallest value in the right subtree.

Only local restructuring is needed.

No conversion needed.

Recap: two-child deletion: find inorder successor (leftmost node in right subtree), copy its value up, delete the successor (which has at most one child).

Self-balancing BSTs (AVL, Red-Black) guarantee

Even balanced trees need O(log n) for search.

Correct — rotations keep height at O(log n) regardless of insertion order.

Space is O(n) for any BST.

Uniqueness is the programmer's responsibility, not the tree's.

Recap: AVL/Red-Black perform rotations after each insert/delete to keep the tree balanced. This guarantees O(log n) worst case — unlike a plain BST.

Python's sortedcontainers.SortedList uses a BST-like structure to

Hash tables and sorted lists serve different purposes.

Correct — backed by a B-tree variant for cache efficiency.

Sorted trees still need O(log n) for access.

That's a hash map, not a sorted tree.

Recap: when you need both sorted order AND O(log n) insert/delete, use a balanced BST or sortedcontainers. When you only need O(1) lookup, use a hash map.

← Previous Next →