5

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.

3
  • I don't think that's in-order, according to Wikipedia. Feb 13, 2013 at 15:40
  • 1
    I just wrote a program to verify it. It seems there is no problem for the in-order traversal. Could you please give the in-order traversal for the example tree to let me double-check it?
    – Fihop
    Feb 13, 2013 at 15:49
  • 1
    It appears I was mistaken. That looks correct, sorry. Feb 13, 2013 at 17:29

4 Answers 4

2

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;
}
4
  • What is time & space complexity of this algorithm? O(n)?
    – AnV
    Apr 18, 2018 at 18:51
  • @AnV It can't be O(n). it would be some factor of O(logn). Apr 19, 2018 at 5:56
  • We need to create nodes for all the N elements in the array, and then attach them to their parents while coming back. So I thought TC would be O(n). Can you please explain how it comes out to be factor of O(logn)?
    – AnV
    Apr 19, 2018 at 8:38
  • @AnV sorry! dont know what I was thinking when I wrote the above comment. upper bound on time complexity of above method is O(n3). We do a linear scan in search and then left and right subtrees. We can get it to O(n2) if we can use a look-up table in search_Arr Apr 23, 2018 at 6:50
0

Actually, the idea is simple, you just need to make sure that the traverse sequence is correct or not. For example, you want to do the in-order traversal, you can simply think like that: From left to right, from down to top.

  1. Traverse to the left bottom(5), then traverse to the right(20) of the same node.

  2. Traverse from bottom(10) to top(50).

  3. Do the same thing in the left.

To the lever-order, you can just traverse from top to bottom, from left to right, step by step.

0
            static tree MakeTreeFromInorderAndLevelOrder(int[] inorder,int[] lorder,int s,int n,int cnt1) {
    if(s>n || s>=inorder.length || n>=inorder.length || cnt1>=inorder.length) {
        return null;
    }
    int mIndex = Search(lorder[cnt1],inorder,s,n);
    tree t = new tree(lorder[cnt1]);

    cnt1 = 2*cnt1 + 1;
    t.left = MakeTreeFromInorderAndLevelOrder(inorder,lorder,s,mIndex-1,cnt1);
    //Boundary case
    if(cnt1<inorder.length && t.left==null) {
        t.right =   MakeTreeFromInorderAndLevelOrder(inorder,lorder,mIndex+1,n,cnt1);
    }
    else {
    cnt1 -=1;
    cnt1 /=2;
    cnt1 = 2*cnt1 + 2;
    t.right = MakeTreeFromInorderAndLevelOrder(inorder,lorder,mIndex+1,n,cnt1);
    //Boundary case
    if(t.right ==null && cnt1<inorder.length) {
        t.left = MakeTreeFromInorderAndLevelOrder(inorder,lorder,s,mIndex-1,cnt1);
    }
    }
    return t;
}
1
  • Hello and welcome to stackoverflow! However, I don't see how this is an answer to the question. The poster asked whether someone can verify the correctness of his algorithm, not for an implementation. If you think your implementation somehow provides this verification, please explain this in your answer. Also, please make sure your answer is well formatted and readable.
    – A. Donda
    Feb 15, 2014 at 16:30
0
    node *construct (in, s, e, level) 
    {
      while (level order has element)
      {
          make the root by taking the first element from level order
          find the index of root->Val in in order.

          segregate the elements of left subtree and right subtree (make sure while 
          segregating from level order the order of element should be same)  call them
          leftLevel[] and rightLevel[]

          construct tree by recursively calling
          root->left  = construct(inorder,s, index-1, leftLevel);
          root->right = construct(inorder, index+1, e, rightlevel);
          return root;
      }
 }

Segregation of elements will require O(n) using hashtable so the overall complexity will be O(nlogn) in balance tree but it will go O(n^2) when tree is unbalanced.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.