Binary Trees


A binary tree is a tree in which each node refers to zero, one, or two dependent nodes. A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree. Binary trees are one kind of ordered tree because the children are ordered as left child node and right child node. There is a one-to-one mapping between binary trees and general ordered trees.



A binary tree may be constructed by means of taking an initial word and creating children of words such that each child is the parent concatenated, either at the start or end with another letter, such that the child is also a valid word.

With the initial word being I, a binary tree may be constructed leading to the words SPINE.

  • I
  • IN
  • PIN
  • SPIN