The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Tree

Problem :-
Implement an algorithm to insert a node in a Binary Search Tree ( BST ).

Solution :-
We need to follow the properties of Binary Search Tree ( BST ) to insert a node at an appropriate place in the tree. We use a recursive algorithm to traverse through different subtrees by comparing the value of the parent node ( P ) and the value of the node to be inserted ( N ). For e.g, if N -> data < P -> data , the new node will be inserted in the left subtree of P . So, we move to the left subtree and follow the same step. This process continues till we reach a node with 0 or 1 child where we can insert the new node.
Following figure illustrates how nodes are inserted in a BST :

inserting nodes in a Binary Search Tree

#include<iostream>
using namespace std;

// node structure
typedef struct tree_node {
   int value;
   struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
   node *new_node = new node;
   new_node->value = value;
   new_node->left = NULL;
   new_node->right = NULL;
   return new_node;
}

// inorder traversal of a tree
void inorderTraversal(node *ptr) {
   if(ptr == NULL)
      return;
   else {
      inorderTraversal(ptr->left);
      cout<<ptr->value<<"\t";
      inorderTraversal(ptr->right);
   }
}

// Node Insertion
node *insertNode(node *ptr,int data) {
   if (ptr == NULL)
      return getNewNode(data);
   if (data <= ptr->value) // node will be inserted in left subtree
      ptr->left = insertNode(ptr->left,data);
   else // node will be inserted in right subtree
      ptr->right = insertNode(ptr->right,data);
   return ptr;
}

// main
int main() {
   node *root = NULL;
   root = insertNode(root,31);
   insertNode(root,16);
   insertNode(root,45);
   insertNode(root,24);
   insertNode(root,7);
   insertNode(root,19);
   insertNode(root,29);
   cout<<"\nInorder traversal :-\n";
   inorderTraversal(root);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Trees
* Implement the inorder , preorder and postorder traversal mechanisms of a tree
* Implement an algorithm to insert a node in a Binary Search Tree ( BST )
* Implement an algorithm to find the height of a Binary Tree
* Implement an algorithm to get the level of a node in a Binary Tree assuming root node to be at level 1
* Get the root to leaf path in a Binary Tree such that the sum of the node values in that path is minimum among all possible root to leaf paths
* Print all the ancestors of a given node in a Binary Tree
* Replace all the node values with the sum of the node values of ancestral nodes in a Binary Tree
* Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree
* Given a Binary Tree, create another tree which is a mirror image of the given tree
* Construct a tree, given its inorder and preorder traversals
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Tree
* Compute the Diameter of a given Binary Tree
* Check if a given tree is a Binary Search Tree ( BST )