A node based implementation of a tree is dynamic data sturctures that provide a hierarchical organization of data. All trees are hierachical in nature, mneaning that therer is a “parent-child” relationship that exists between the nodes in a tree.
A binary tree is a set of nodes that is either empty or partitioned into a root node and one or two subsets that are binary subtrees of the root. Each node has at most two children, the left child and the right child. A binary search tree is a binary tree in which the key in any node n is greater than the key in every node in n’s left subtree, but less than the value in every node in n’s right subtree. Each nodes position is based on it’s relationship with other nodes.
The purpose of binary search trees is to provide an efficient search operation for quickly loading a specific item contained in a tree. Binary search trees has a recursive nature, recursion is useful in the implementation of its operations. As is typical, the recursive methods are not public, since they require parameters that are a part of the underlying data structure.
The binary search tree is structured such that for each interior node root
key < root.key are stored in the left subtree of root
key > root.key are stored in the right subtree of root