Binary tree

A binary tree is an ordered tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One use of binary trees is as binary search trees.

There is a one-to-one mapping between general ordered trees and binary trees which Lisp uses to represent general ordered trees as binary trees. Each node N in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the node corresponding to the first child of N, and the right child of N' is the node corresponding to the N's next sibling --- that is, the next node among N's parent's children.

One way of thinking about this is that each node's children are in a linked list, chained together with their right fields, and the node only has a pointer to the beginning of this list.