Trees and Heaps

A tree is a hierarchical data structure consisting of nodes connected by edges, starting from a single root node and branching downward without forming any cycles. Each node other than the root has exactly one parent and may have any number of children; a node with no children is called a leaf, and the length of the longest path from the root to a leaf defines the tree's height, while a node's depth is its distance from the root. A binary tree restricts each node to at most two children, conventionally called the left and right child. Binary trees are further classified by shape: a full binary tree has every node with either zero or two children, a complete binary tree has every level filled except possibly the last, which is filled from left to right, and a perfect binary tree has every level completely filled.