Binary trees

A binary tree is one in which each node has a maximum of two children. Binary trees are very common and we shall use them to build up a BST implementation in Python.

The following figure is an example of a binary tree with 5 being the root node:

Each child is identified as being the right or left child of its parent. Since the parent node is also a node by itself, each node will hold a reference to a right and left node even if the nodes do not exist.

A regular binary tree has no rules as to how elements are arranged in the tree. It only satisfies the condition that each node should have a maximum of two children.

Binary search trees

A binary search tree (BST) is a special kind of a binary tree. That is, it is a tree that is structurally a binary tree. Functionally, it is a tree that stores its nodes in such a way to be able to search through the tree efficiently.

There is a structure to a BST. For a given node with a value, all the nodes in the left sub-tree are less than or equal...