Trees, Heaps and Tries

Full: every node has 0 or 2 children. Complete: every level filled except possibly the last, which is filled left to right. Perfect: all internal nodes have 2 children and all leaves are at the same depth.

2^(h+1) − 1 nodes (height counted in edges), with 2^h leaves.

⌊log₂ n⌋, achieved by a complete tree; the maximum is n − 1 for a degenerate, list-like tree.

Children of i are at 2i + 1 and 2i + 2; the parent of i is ⌊(i − 1)/2⌋. No pointers are needed.

Preorder: root, left, right. Inorder: left, root, right. Postorder: left, right, root.

Postorder, because children are processed before their parent, so no node is freed while still needed.