Question: A tree has a special property where leaves are represented with ‘L’ and non-leaf with ‘N’. Each node has either 0 or 2 children. If given preorder traversal of this tree, construct the tree.

Example:
Given Pre Order string => NLNLL

o/p tree:
Answer: Firstly, we should see how pre-order traversal is arranged. Pre-order traversal means first put root node, then pre order traversal of left subtree and then pre order traversal of right subtree. As shown in below figure:

In normal scenario, it’s not possible to detect where left subtree ends and right subtree starts using only pre-order traversal. But here, we are given a special property. Since every node has either 2 children or no child, we can surely say that if a node exists then its sibling also exists. So every time we are computing a subtree, we need to compute its sibling subtree as well.

Secondly, whenever we get ‘L’ in the input string, that is a leaf so we can stop for a particular subtree at that point. So after this ‘L’ node (left child of its parent ‘L’), it’s sibling starts. If ‘L’ node is right child of its parent, then we need to go up in the hierarchy to find next subtree to compute.

Keeping above invariant in mind, we can easily determine, when a subtree ends and next start. It means that we can give any start node to our method and it can easily complete the subtree it generates w/o going outside its nodes.

We just need to take care, that we are passing correct start nodes to different subtrees.

Code:
tree* newnode(char c)
{
tree *node = new(tree);
node->val = c;
node->left = node->right = NULL;
return node;
}

tree* construct_tree(char* A, int *i)
{
//Boundary Condition
if (A == NULL){
return NULL;
}

tree *node = newnode(A[*i]);
//On reaching leaf node, return
if (A[*i] == 'L'){
return node;
}

//Populate left sub tree
*i = *i + 1;
node->left = construct_tree(A, i);

//Populate right sub tree
*i = *i + 1;
node->right = construct_tree(A, i);

return node;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.