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 :-
Construct a tree, given its inorder and preorder traversals.

Solution :-
Suppose the inorder array is { 4 , 2 , 5 , 1 , 6 , 3 } and the
                 preorder array is { 1 , 2 , 4 , 5 , 3 , 6 }
We will pick up the first element 1 from preorder array and search that element in the inorder array .
1 becomes the root element and all elements on the left of 1 in the inorder array i.e { 4 , 2 , 5 } forms the left subtree and elements on the right { 6 , 3 } forms the right subtree of 1. Then we look for second element 2 in the preorder array and recursively construct the subtrees of that element. This process is repeated till the entire preorder array is traversed and the complete tree is constructed. Following figure demonstrates the procedure.

construct a tree given its inorder and preorder traversal

#include<iostream>
using namespace std;

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

// Find the index of value in arr[start ... end]
int search(int arr[], int start_idx, int end_idx, int value) {
   int i;
   for(i = start_idx; i <= end_idx; i++) {
         if(arr[i] == value)
            return i;
   }
}

// 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);
   }
}

// construct the tree from its inorder and preorder traversals
node* constructTree(int inorder[],int preorder[],int inorder_start,int inorder_end)
{
static int preorder_idx = 0; if(inorder_start > inorder_end) //bound check return NULL; // create a new node using the value in the current index of the preorder array node *tree_node = getNewNode(preorder[preorder_idx++]); // leaf node (no children) if(inorder_start == inorder_end) return tree_node; // Find the index of this node in the inorder array int inorder_idx = search(inorder,inorder_start,inorder_end,tree_node->value); // construct the left and right subtrees of this node tree_node->left = constructTree(inorder,preorder,inorder_start,inorder_idx-1); tree_node->right = constructTree(inorder,preorder,inorder_idx+1,inorder_end); return tree_node; } // main int main() { int inorder[] = {4, 2, 5, 1, 6, 3}; int preorder[] = {1, 2, 4, 5, 3, 6}; int length = 6; node *root = constructTree(inorder, preorder, 0, length - 1); cout<<"\n Inorder traversal of the constructed tree is \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 )