Binary trees

ACompressed recap

🧾

Binary trees have left and right subtrees. Strict: 0 or 2 children; complete: left-packed levels; perfect: every level full; skewed: a path. Counts: level i ≤ 2ⁱ; height h holds h + 1 … 2ʰ⁺¹ − 1 nodes; n nodes need height ⌊log₂ n⌋ … n − 1; n₀ = n₂ + 1; n + 1 NULL pointers. Storage: linked nodes for any shape, or arrays with 2i + 1 / 2i + 2 / ⌊(i − 1)/2⌋ (0-based) or 2i / 2i + 1 / ⌊i/2⌋ (1-based), compact only for complete trees.

BMerged rule card

4.2.1 Strict/full, complete and perfect binary trees

• Binary tree: each node has a left and a right subtree (possibly empty); left ≠ right.
• Strict/full: every node 0 or 2 children (some books: full = perfect).
• Complete: all levels full except the last, which is left-packed.
• Perfect: all levels full (strict + complete).
• Skewed: one child per node; height n − 1.

4.2.2 Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum height

• Level i: ≤ 2ⁱ nodes; height h: h + 1 ≤ n ≤ 2ʰ⁺¹ − 1 (edges).
• n nodes: ⌊log₂ n⌋ ≤ height ≤ n − 1.
• n₀ = n₂ + 1; strict tree with i internal nodes: i + 1 leaves, 2i + 1 nodes.
• n + 1 NULL pointers.
• Nodes convention: replace h by h − 1.

4.2.3 Representations: linked nodes vs array indexing (both 0-based and 1-based formulas)

• Linked: struct tnode { data; *left; *right; }; empty subtree = NULL.
• 0-based: children 2i+1, 2i+2; parent ⌊(i−1)/2⌋.
• 1-based: children 2i, 2i+1; parent ⌊i/2⌋.
• Array form compact only for complete trees; height h may need 2ʰ⁺¹ − 1 slots.
• Heaps use arrays; search trees use links.

CInterleaved GATE-style questions

Q1NAT1 markLeaves

A strict binary tree has 40 internal nodes. How many leaves?

Numerical answer: ________

Q2NAT2 marksNodes

A binary tree has n₁ = 8 and n₀ = 12. How many nodes does it have?

Numerical answer: ________

Q3MCQ1 markHeight

The minimum height (edges) of a binary tree with 64 nodes is:

• (A) 5
• (B) 6
• (C) 63
• (D) 7

Q4MCQ2 marksComplete

A complete binary tree has 11 nodes. How many of them have exactly one child?

• (A) 0
• (B) 5
• (C) 2
• (D) 1

Q5NAT1 markIndexing

0-based array: index of the left child of node 6?

Numerical answer: ________

Q6NAT1 markLevels

Maximum number of nodes on level 7 (root at level 0)?

Numerical answer: ________

Q7MSQ2 marksShapes

Which are true?

• (A) A complete binary tree has height ⌊log₂ n⌋.
• (B) A strict binary tree has an odd number of nodes.
• (C) A skewed tree is complete.
• (D) A perfect binary tree of height h has 2ʰ leaves.

Q8NAT2 marksArray space

Worst-case array slots needed for a binary tree of height 6 (edges) stored by level index?

Numerical answer: ________

Q9MCQ1 markNodes convention

In the nodes convention (single node has height 1), the maximum number of nodes of height h is:

• (A) h
• (B) 2ʰ − 1
• (C) 2ʰ⁺¹ − 1
• (D) 2ʰ

DAnswer Vault