Non-Linear Data Structures :: Binary Tree

The first non-linear data structure and most important to understand is the binary search tree. This structure consists of a main node which is called the root and sub nodes which are called children. Each parent node has children nodes starting at the root and going to the bottom of the tree. Binary Search trees work by having a left child and a right child pointer. This does not mean that every parent node will have 2 children. The number of children depend on the values of each node that are inserted into the tree. The first value that is inserted into the tree is the root. From the root each value inserted must be checked against it; if the value is greater than the root then it would become the right child if it were less than the root it would become the left child. This goes on through the entire tree. NO left child will ever be greater than or equal to its parent or sibling.

The following tree was created by inserting these values in order. (10,15,13,24,4,7,9,5,2)