Trees, binary search trees and binary heaps: heights and operation costs

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Cost of deleting the last node of a singly linked list with only a head pointer? from Lesson 0.2.1
• How many bits does n have? from Lesson 0.1.2
• Σ 2ⁱ for i = 0..k? from Lesson 0.1.2

1 · The Hook

🎣

Search trees and heaps make many operations cost about log n instead of n, because a balanced tree with a million nodes is only about 20 levels tall. Heapsort (Lesson 3.2.3) and Dijkstra's and Prim's algorithms (Phase 6) all run on binary heaps.

2 · Predict First

🤔

Insert 10, 20, 15, 30, 40 one at a time into an empty max-heap (stored as an array, each new key placed at the end and swapped upward while it is bigger than its parent). What is the final array?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

[40, 30, 15, 10, 20], after 5 swaps in total.

Binary trees

Each node has at most two children. Height h = number of edges on the longest root-to-leaf path (a single node has height 0).

• Level i holds at most 2ⁱ nodes.
• A tree of height h holds at most 2ʰ⁺¹ − 1 nodes.
• n nodes need height at least ⌊log n⌋; at most n − 1 (a chain).
• A complete binary tree fills every level except possibly the last, which is filled from the left.

Binary search trees (BST)

For every node: keys in the left subtree < node's key < keys in the right subtree.

• Search, insert, delete follow one root-to-leaf path: O(h).
• h is about log n if balanced, but up to n − 1 if keys arrive in sorted order (a chain).
• Inorder traversal (left, node, right) lists the keys in sorted order.

Binary heaps (max-heap)

• Shape: a complete binary tree, stored in an array A[1..n] level by level.
• Order: every parent ≥ its children, so the maximum is at A[1].
• Index arithmetic (1-based): children of i are 2i and 2i + 1; parent of i is ⌊i/2⌋. Leaves are positions ⌊n/2⌋ + 1 … n.
• Height = ⌊log n⌋.

A min-heap is the same with ≤: the minimum is at the root.

4 · Visual

Max-heap after inserting 10, 20, 15, 30, 40           array (1-based)
            40                                        index: 1  2  3  4  5
          /    \                                      value: 40 30 15 10 20
        30      15                                    children of 2: 4 and 5
       /  \                                           parent of 5: 2
     10    20

5 · Worked Examples

Example 1 Easy

A binary tree has height 4. What is the maximum number of nodes?

Solution

2⁵ − 1 = 31.

Example 2 Medium

In a max-heap stored in A[1..20], what are the indices of the children and parent of node 7?

Solution

Children 14 and 15; parent ⌊7/2⌋ = 3.

Example 3 GATE

Keys 1, 2, 3, 4, 5, 6, 7 are inserted in that order into an empty BST. What is its height?

Solution

Each key goes to the right of the previous: a chain of 7 nodes, height 6.

6 · GATE Traps

⚠️

• Height counts edges here (one node = height 0). Some questions count levels; read carefully.
• BST costs are O(h), and h can be n − 1.
• Heap index rules (2i, 2i + 1, ⌊i/2⌋) are for 1-based arrays.
• A heap is not sorted: only parent ≥ child holds.

7 · Memory Hook

🧠

"Children at 2i and 2i+1, parent at half."

8 · Connect the Dots

This lesson priced trees and heaps. Last recap lesson: graphs, their vocabulary and the two ways to store them, which decide the cost of every graph algorithm in Phase 6.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markMax nodes

Maximum number of nodes in a binary tree of height 6?

Numerical answer: ________

Q2NAT1 markHeap index

In a 1-based max-heap of 50 elements, what is the index of the parent of node 37?

Numerical answer: ________

Q3NAT2 marksHeap insertion

Insert 3, 8, 1, 9, 4, 7 one by one into an empty max-heap. How many swaps happen in total?

Numerical answer: ________

Q4MCQ1 markBST

Which traversal of a BST lists its keys in ascending order?

• (A) Inorder
• (B) Postorder
• (C) Preorder
• (D) Level order

Q5NAT1 markLeaves

A max-heap has 31 elements in A[1..31]. How many of them are leaves?

Numerical answer: ________

10 · Rule Card

• Height h (edges): ≤ 2ⁱ nodes at level i; ≤ 2ʰ⁺¹ − 1 nodes; n nodes → h ≥ ⌊log n⌋.
• BST: left < node < right; operations O(h); inorder = sorted; sorted inserts make a chain.
• Max-heap: complete tree, parent ≥ children; 1-based children 2i, 2i+1, parent ⌊i/2⌋; leaves ⌊n/2⌋+1..n.
• Heap: max O(1); insert/extract O(log n); build O(n).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

binary treeheight (in edges)complete binary treebinary search treeinorder traversalmax-heap and min-heap1-based heap indexingsift upsift downheap operation costs

12 · Answer Vault