—The simplest form of tree is a Binary Tree. —A Binary Tree consists of a node (called the root node) and Left and right subtrees. Both the subtrees are themselves binary trees. A node can’t have more than 2 children. A binary tree is called —Full binary tree if it has all leaves are on the same level and every node has either zero or two children. Similarly, a binary tree is called complete binary tree, if its leaves are filled from left to right on one level before moving to next level.

  • —Skewed binary tree: Contains only left or right children.
  • —Similar: Two trees with same structure and different data.
  • —Copy or identical: Same structure and same data.

—The representation of a binary tree structure is relatively straightforward. We need a variable to store the data at the node and two pointers to the left and right subtrees.
struct Node {
   int data
   Node *left
   Node *right 

Binary Search Trees

—When we store ordered data in an array, we have a very efficient search algorithm, i.e. the binary searching. —However, we have very inefficient insertion and deletion algorithms that require shifting data in the array. —To provide efficient insertions and deletions, we developed the linked list. —The problem with linked lists, however, is that their search algorithms are sequential searches, which are very inefficient.

—Can we get the best of both worlds (i.e., efficient search, insertion, and deletion algorithms)? —The binary search tree is our answer! —

The binary search tree is a binary tree with the following properties:

  • All items (keys) in the left subtree are less than the root’s key.
  • All items (keys) in the right subtree are greater than the root’s key.
  • Each subtree is, itself, a binary search tree.
Assume each node of a binary tree stores a data item. Assume data items are of some type that can be ordered and all items are distinct (No two items have the same value).
  • A binary search tree is a binary tree such that
  • For every node X in the tree:
    • the values of all the items in its left subtree are smaller than the value of the item in X
    • the values of all items in its right subtree are greater than the value of the item in X.

Here you can see the basic structure of a binary search tree.

Operations on Binary Search Trees

—Binary trees offer short paths from root. —A node has up to two children. —Data is organized by value:

  • Insertion
  • Search
  • Traversal
  • Deletion
  • —Find Minimum: Find the item that has the minimum value in the tree
  • —Find Maximum: Find the item that has the maximum value in the tree
  • —Print: Print the values of all items in the tree, using a traversal strategy that is appropriate for the application
  • —Successor
  • —Predecessor

A more detailed topic on Operations of Binary Search Trees will be presented later.

Inserting an item in BST

—The first value inserted goes at the root. —Every node inserted becomes a leaf. —Insert left or right depending upon value.

void Insert(Node *&tree, int item) //’tree’ points to ‘root’ node in 				        // the beginning
 if(tree == NULL) {  // base case
   tree = new Node;
   tree->right = NULL;
   tree->left = NULL;
   tree->data = item;
 else if(item < tree->data)
   Insert(tree->left, item);
   Insert(tree->right, item);

Note: —we have written this definition in a way that ensures that no two entries in a binary search tree can have equal keys. —Although it is possible to modify the definition to allow entries with duplicate keys, it makes the algorithms somewhat more complicated. —If duplicates need to be accounted for, they can be stored in another data structure (e.g., list).

The binary search tree property does not say what happens with the elements with the same key. In our examples, all the keys will be distinct but in practice it is important to cover the case of multiple elements with the same key (duplicate keys). The duplicate keys can all be kept in the left subtree, or all in the right subtree. It doesn’t matter which we choose, but it matters that the choice is the same for the whole implementation. Another issue: with duplicate keys, it is important to have extra operations in the interface: getAll, and removeAll

Tagged with: C/C++ languageData structures

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.