Binary Trees

Definition

• A Binary Tree: each node has at most 2 children, conventionally called left and right child

Types of Binary Trees

• Full Binary Tree: every node has either 0 or 2 children (never exactly 1)
• Complete Binary Tree: all levels fully filled except possibly the last, which fills left to right (basis of array-based Heap implementation)
• Perfect Binary Tree: all internal nodes have 2 children AND all leaves are at the same level
• Skewed Binary Tree: every node has only one child (degenerates into a linked list — worst case for performance)
• Balanced Binary Tree: height difference between left/right subtrees is bounded (e.g., AVL Tree)

Binary Search Tree (BST) — Special Case

• Ordering property: for every node, left subtree < node < right subtree
• Enables O(log n) search if balanced; degrades to O(n) if skewed (e.g., inserting already-sorted data into a naive BST)

Array Representation (for Complete Binary Trees, e.g., Heaps)

• For node at index i: $\text{left child} = 2i+1$, $\text{right child} = 2i+2$, $\text{parent} = \lfloor (i-1)/2 \rfloor$

Exam Angle / MCQ Trap

A classic trap: inserting sorted data (1,2,3,4,5) into a plain BST produces a skewed tree (effectively a linked list) with O(n) search — this is exactly why self-balancing trees like AVL were developed.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: Full vs Complete — the Classic Trap (MCQ)

2024, Paper I, Q18 (1 mark) — Regarding Binary Trees, which of the following is true?

• A. Every binary tree has two states: full and complete.
• B. Every binary tree that is full is also a complete binary tree.
• C. All complete binary trees are likewise full binary trees.
• D. None of these ✓

MCQ Trap: neither (A), (B) nor (C) holds. A full binary tree (every node has 0 or 2 children) need not be complete — it can be full but lopsided/unbalanced. A complete binary tree (levels filled left-to-right) need not be full — a node in the last level can have exactly one child. "Full" and "complete" describe two independent properties, not a hierarchy — this page's own Definition section already lists them separately, and this MCQ is exactly the trap that tests whether that distinction actually sank in.

📝 Exam Practice: BST Shape Under Random vs Adversarial Insertion

2018, Paper I, Q5(c) (7 marks) — Random insertion of nodes into a binary search tree would result in what types of tree shape. Elaborate.

Model answer: If keys are inserted into a BST in a random order (each of the n! orderings equally likely), the resulting tree is, on average, reasonably well-balanced — expected height is O(log n) (specifically ≈ 2·ln(n)), giving O(log n) expected search/insert/delete. This is because random order tends to place roughly half the keys smaller and half larger than the root at each level, similar to why randomized quicksort behaves well on average.

However, this is only an average-case guarantee, not worst-case: for an unlucky order — particularly already-sorted (ascending/descending) input — the tree degenerates to a fully skewed, linked-list shape with height O(n), giving O(n) worst-case operations.

Exam angle: this is precisely why self-balancing trees (AVL, Red-Black) exist — to guarantee O(log n) height regardless of insertion order, rather than relying on a plain BST and hoping the input happens to arrive in random order.

📝 Exam Practice: Defining "Balanced" for AVL vs a Plain BST

2018, Paper I, Q6(a) (4 marks) — Define balanced tree both for AVL and Binary search tree.

Model answer:

• Balanced AVL Tree: a self-balancing BST in which, for every node, the balance factor — height(left subtree) − height(right subtree) — is restricted to exactly −1, 0, or +1. Any insertion/deletion pushing a node outside this range triggers rotations (LL, RR, LR, RL) to restore it, guaranteeing O(log n) height.
• Balanced BST (general sense): more loosely, a BST is "balanced" if its height is O(log n) relative to n — left and right subtrees roughly comparable in size at every node. A plain BST has no formal mechanism enforcing this; it depends entirely on insertion order, unlike AVL/Red-Black trees which formally guarantee it via a checkable invariant after every operation.

Key reasoning point: don't conflate the two — "balanced" for a plain BST is a description of a lucky outcome, while "balanced" for an AVL tree is an enforced invariant.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-I · Q5(c) · 7 marks

Q. Random insertion of nodes into a binary search tree results in what type of tree shape? Elaborate.

Ans.

• The shape depends on the order of insertion, because each new key is placed by comparing with existing nodes.
• Random order: the tree tends to be reasonably balanced. Its expected height is O(log n) (about 1.39 log₂ n), so search, insert and delete average O(log n).
• Sorted or reverse-sorted order: every key goes to the same side, and the tree degenerates into a skewed tree (a linked list) of height n. Operations become O(n).
• Example: inserting 10, 20, 30, 40 gives a right-leaning chain, while 30, 10, 40, 20 gives a bushy tree.
• Remedy: use self-balancing trees (AVL or red-black), which guarantee O(log n).

MCQs

2024 P-I · Q18. Regarding binary trees, which of the following is true?

• (A) Every binary tree has two states: full and complete
• (B) Every binary tree that is full is also a complete binary tree
• (C) All complete binary trees are likewise full binary trees
• (D) None of these ✅
• Answer: (D) None of these.
• Why: a binary tree need not be full or complete, so (A) is false. A full tree (every node has 0 or 2 children) can be uneven and is then not complete, so (B) is false. A complete tree can have a node with one child, so it need not be full, so (C) is false.