A binary tree is a data structure composed of zero or more nodes. Each node contains:
- A value (some kind of data item)
- A reference or pointer to a left child (may be null)
- A reference or pointer to a right child (may be null)
A binary tree may be empty, in which case it has no nodes. If it is not empty, a binary tree has a root node.
Every node in the binary tree is reachable from the root node by a unique path.
A node with neither a left child nor a right child is called a leaf.
The size of a binary tree is the number of nodes in it.
The depth of a node is its distance from the root.
The depth of a binary tree is the depth of its deepest node.
A binary tree is said to be balanced if every level above the lowest is “full” (contains 2N nodes). In most applications, a reasonably balanced binary tree is desirable.
Next: Hash Tables