construct a binary tree from in-order and level-order traversal

Question

Firstly, I'd like to state this is not a homework. I'm preparing an interview and encountering this problem. I guess we can pass the definition of in-order and level-order traversal. :-).

For example:

      50
   /      \
 10        60
/  \       /  \
5   20    55    70
        /     /  \
      51     65    80

The in-order and level-order traversal of the above tree are:

5, 10, 20, 50, 51, 55, 60, 65, 70, 80

50, 10, 60, 5, 20, 55, 70, 51, 65, 80

My idea:

(1) traversal the level-order array to find out the first element which appears in the in-order array. We call this element as current root.

(2) find the index of current root in the in-order array. The in-order array is separated by the index. The left side of the in-order array is the left sub-tree of the current root and the right side of the in-order array is the right sub-tree of the current root.

(3) update the in-order array as its left side and then go to step 1.

(4) update the in-order array as its right side and then go to step 2.

Take the above tree as an example.

(1) 5 is the first element appears in the in-order array. 

(2) [50 ...60] is the left sub-tree of 5 and [20 ... 80] is the right sub-tree of 5. 

(3) update the in-order array as [50 ... 60]

    (1) 10 is the first element appears in [50 10 60].

    (2) [50] is the left sub-tree of 10 and [60] is the right sub-tree of 10.

    (3) update ...

Can anyone help me verify my solution? And really appreciate if giving another one.

Answer 1

I think you are on the right track. below is a working code which I worked out using your data.

/*
//construct a bst using inorder & levelorder traversals.
//inorder    - 5, 10, 20, 50, 51, 55, 60, 65, 70, 80
//levelorder - 50, 10, 60, 5, 20, 55, 70, 51, 65, 80
         50
      /      \
    10        60
   /  \       /  \
  5   20    55    70
            /     /  \
          51     65    80
 */
struct node *construct_bst3(int inorder[], int levelorder[], int in_start, int in_end)
{
    static int levelindex = 0;
    struct node *nnode = create_node(levelorder[levelindex++]);

    if (in_start == in_end)
        return nnode;

    //else find the index of this node in inorder array. left of it is left subtree, right of this index is right.
    int in_index = search_arr(inorder, in_start, in_end, nnode->data);

    //using in_index from inorder array, constructing left & right subtrees.
    nnode->left  = construct_bst3(inorder, levelorder, in_start, in_index-1);
    nnode->right = construct_bst3(inorder, levelorder, in_index+1, in_end);

    return nnode;
}