Binary Tree

Common terminology	CLRS	Diagram
Full Binary Tree
Complete Binary Tree	Nearly Complete Binary Tree
Perfect Binary Tree	Complete Binary Tree

Common terminology will be used below

Notation: n nodes, l leaves, h height, n_{k} nodes at depth k,

• The height (depth) of a node is the number of edges on the longest simple downward path from the root to the node.

• The height $h$ of a tree is the number of edges on the longest simple downward path from the root to a leaf.

Complete Binary Tree

• $2^h\le n\le 2^{h+1}-1$
  • $n_k=2^k$ (where $k<h$)
  • $1\le n_h\le 2^h$
• $l=\lceil n/2\rceil$
• $h=\lfloor \lg n\rfloor$

Perfect Binary Tree

• $n=2^{h+1}-1$
  • $n_k=2^k$
• $l=2^h=\lceil n/2\rceil$
• $h=\lfloor \lg n\rfloor$

Traversal

• Preorder: Root, Left, Right
• Inorder: Left, Root, Right
• Postorder: Left, Right, Root