A fundamental data structure, there are multiple ways of defining binary trees. Mathematically speaking, a binary tree is a connected, undirected, finite graph with no cycles, and no vertex edge of degree greater than three.

For most computer science applications, binary trees are rooted. A special node, r, of degree at most two is called the root of the tree. For every node, u≠r, the second node on the path from u to r is called the parent of u. Any nodes adjacent to u is referred to as the child of u. The majority of the binary trees in this section are ordered so, we differentiate between the left and right child of u.

Binary trees are typically drawn from the root down, with the root at the top of the drawing and the left and right children respectively given by left and right positions (see Fig.1). Figure 2 shows a binary tree with nine nodes.

As binary trees are so important, there is terminology for them:

• The depth of a node, u, in a binary tree is the length of the path from u to the root of the tree
• If a node, w, is on the path from u to r, then w is referred to as the ancestor of u and u is the descendent of w.
• The subtree of a node, u, is the binary tree that is rooted at u and contains all of u's descendents.
• The height of a node, u, is the length of the longest path from u to one of its descendents.
• The height of a tree is the height of its root.
• A node, u, is a leaf if it has no children

It is common practice to think of the tree as being augmented with external nodes. Any node that does not have a left child has an external node as its left child, and, correspondingly, any node without a right child has an external child as its right child (see Fig.3). We can verify by induction that a binary tree with n≥1 real nodes has n+1 external nodes.

• Basic Binary Tree
• Unbalanced Binary Search Tree