Binary Trees

Trees consist of nodes where data is stored. The nodes are arranged in levels. The top level contains exactly one node. It is called "root node". Except for the root node, each node is connected to exactly one node in the level immediately above it. There are no other connections between the nodes.

Tree terminology: If n is a node, and p is the node connected to it in the preceding level, then we say that node p is the "parent" of node n and node n is a "child" of node p. The root node does not have a parent because there are no nodes above it.

In pictures the nodes are represented as circles and the connections are drawn as edges that connect the circles. See below.

A tree is said to be a "Binary Tree" if each node is connected to no more than two nodes in the level below it. Each node has at most two children. In addition the nodes on a level are ordered from left to right. A node can have a "Left Child" or a "Right Child", or both a left and a right child, or no children at all. A node without any children is said to be a "leaf".

In the binary tree above, the node containing 16 has a left child, but has no right child. And the node containing 14 has a right child, but has no left child. The nodes containing 13, 2, and 3 are leaves because they have no children.