CODEWITHSUNDEEP
data-structuresbinary-treeinorder
Fihop
Fihop

Reputation: 3177

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

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.

Upvotes: 5

Views: 4427

Answers (4)

rgaut
rgaut

Reputation: 3579

    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.

Upvotes: 0

badri.coder
badri.coder

Reputation: 147

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

Upvotes: 0

Srikar Appalaraju
Srikar Appalaraju

Reputation: 73588

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

Upvotes: 2

JIANG
JIANG

Reputation: 1

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.

Upvotes: 0

Related Questions