CMPSC 24 Lecture Notes - Lecture 9: Binary Tree
Document Summary
Each node has at most 2 children. Root of the tree is the first top node. Leaves of a tree: nodes with no children. A node that is not a leaf is an "internal node" Degree of a node: number of children nodes attached to it. Number of nodes at a certain level = 2^level. Height from n nodes h = log(n+1) - 1 h ~ o(log(n)) Full binary tree except for that the leaf level may not be full. All the missing nodes of the leaf level are on the right side h = o(log n) + 1"