Binary Trees

Graph Theory · Axiom Academy

A fundamental tree structure where each node has at most two children A binary tree consists of nodes where each node contains: A reference to a left child (or null) A reference to a right child (or null) The topmost node is called the root , and nodes with no children are called leaves . All internal nodes have exactly two children All leaves are at varying depths (not necessarily the same level) This property ensures balanced branching at each node Complete binary trees have special properties: All levels except the last are maximally filled The last level has all nodes as far left as possible Used in heap data structures for efficient array representation Height is minimized for a given number of nodes Perfect binary trees are the most balanced form: All levels are completely filled All leaves are at the same depth A perfect binary tree of height h has exactly 2 h+1 - 1 nodes Every perfect binary tree is also complete and full 5. Properties and Height Bounds Binary trees have several important mathematical properties that govern their structure and efficiency. Maximum nodes at depth d: 2 d nodes (where root is at depth 0) Maximum nodes in tree of height h: 2 h+1 - 1 nodes Minimum height for n nodes: h ≥ ⌈log₂(n+1)⌉ - 1 Maximum height for n nodes: h ≤ n - 1 (degenerate/skewed tree) Number of leaf nodes: For a full binary tree with I internal nodes, there are I + 1 leaf nodes

This is the written version of the interactive lesson above. See the full Graph Theory course.