Special Binary Trees

Knowledge Summary

Full Binary Tree

A binary tree in which every level contains the maximum possible number of nodes.

• A full binary tree of depth h has 2^h - 1 nodes
• The i-th level has 2^(i-1) nodes

Complete Binary Tree

Every level is full except possibly the last, and the nodes on the last level are packed to the left.

Properties (numbering starts from 1):

• Left child of node i: 2i
• Right child of node i: 2i + 1
• Parent of node i: i / 2 (integer division)
• Height of a complete binary tree with n nodes: ⌊log₂n⌋ + 1

Binary Search Tree (BST)

• All values in the left subtree are less than the root value
• All values in the right subtree are greater than the root value
• Inorder traversal produces a sorted sequence

Balanced Binary Tree (AVL Tree)

• For every node, the height difference between its left and right subtrees is at most 1
• Search, insertion, and deletion all have time complexity O(log n)

Heap

• Max heap: parent >= children
• Min heap: parent <= children
• A heap is a complete binary tree
• Used to implement priority queues

Relation Between Numbers of Nodes in a Binary Tree

Suppose there are n₀ nodes of degree 0 (leaves) and n₂ nodes of degree 2:

$n_0 = n_2 + 1$