Binary Trees

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)

ADS 03 P2 K

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.

ADS 03 P2 M

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