Binary Trees

In computer science, a binary tree is a data structure consisting of nodes and links. It is similar to a linked list where each node points (or is linked) to the next node. That node, in turn, points to the next, and so on. This creates a sequence or list of nodes each linked to one parent and to one child. The beginning node has only one link because it has no parent. The ending node also has only one link because it has no child. The nodes in a binary tree however, can have up to 2 children. The structure still has one beginning, but now there are possibly many endings. Large binary lists with random nodes of 0, 1, and 2 children often results in a graph resembling a tree. This is where the name 'binary tree' came from. The starting node is called the root of the tree. And since there are many ending nodes, they are called leaves of the tree. Child nodes are referred to as the left child and the right child - even when there is only one child.

In image 1, the node F has left child B and right child G. Both nodes B and G have F as a parent. Nodes A and D are children of B. Nodes C and E are children of D. Node C and node E have no children which means they are both leaf nodes. The binary tree shown in image 1 has 4 leaves: A, C, E, and H. Node I is the right child of G, while node H is the left child of I. The node F has no parent, so it is the root node.

Types of Binary Tree[edit | edit source]

  • Full binary tree - Every node in the tree has either 0 or 2 children.
  • Perfect binary tree - All interior nodes should have two children and all leaves have the same depth or same level.
  • Complete binary tree - Every level in the tree is completely filled, except possibly the last, and all nodes(leaf nodes) in the last level are as far left as possible.
  • Balanced binary tree - The left and right sub-trees of every node differ in height by no more than 1 called as balancing factor.

Main applications[edit | edit source]

  1. Manipulate hierarchical data
  2. Make information easy to search
  3. Manipulate sorted lists of data
  4. As a workflow for compositing digital images for visual effects
  5. Router algorithms
  6. Form of a multi-stage decision-making