PROGRAMMING INTERVIEWS

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