CIS3355: Business Data Structures
Fall, 2008
 

What is a binary tree and why do we use it?

by Omar Sigala

    A binary tree is a structure used to represent hierarchical data through the use of binary search and link lists.  It is composed of nodes, where each node has a data element, a right pointer and a left pointer These right and left pointers point to lower sub-trees on each side of the node. The following diagram represents a binary tree:

    There also exists a binary search tree (such as the one above). This is a type of binary tree where the nodes have been arranged in an order. The node arrangement is dependent on the values of the data elements and the left and right pointers. For each of the nodes, the left sub-tree should have a value less or equal to the data element value. For the right sub-tree, the value should be higher than the data element. Other important terms that should be considered are the leaves and the internal nodes. The leaves represent the nodes located at the bottom of the tree, while the internal nodes correspond to every node between the origin and leaves of the tree.