Preparation/ConstructTreeFromInorderAndLevelOrder.cpp at master · yukty2000/Preparation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/* GFG
Given inorder and level-order traversals of a Binary Tree, construct the Binary Tree and return the root Node.

Input:
First line consists of T test cases. First line of every test case consists of N, denoting number of elements is respective arrays. Second and third line consists of arrays containing Inorder and Level-order traversal respectively.

Output:
Single line output, print the preOrder traversal of array.

Constraints:
1<=T<=100
1<=N<=100

Example:
Input:
2
3
1 0 2
0 1 2
7
3 1 4 0 5 2 6
0 1 2 3 4 5 6
Output:
0 1 2
0 1 3 4 2 5 6

*/
Node *findAns(int inorder[],int levelOrder[],int iStart,int iEnd,int lStart,int lEnd)
{
    if(iStart>iEnd)
        return NULL;
    if(iStart==iEnd)
        return new Node(inorder[iStart]);
    Node *temp=new Node(levelOrder[lStart]);
    int i=iStart;
    for(;i<=iEnd;i++)
    {
        if(inorder[i]==levelOrder[lStart])
            break;
    }
    int si=i-iStart;
    int llOrder[si];
    int lrOrder[iEnd-i];
    int u=0,v=0;
    for(int j=lStart+1;j<=lEnd;j++)
    {
        int c=0;
        for(int k=iStart;k<i;k++)
        {
            if(inorder[k]==levelOrder[j])
            {
                c=1;
                llOrder[u++]=levelOrder[j];
                break;
            }
        }
        if(c==0)
            lrOrder[v++]=levelOrder[j];
    }
    temp->left=findAns(inorder,llOrder,iStart,i-1,0,u-1);
    temp->right=findAns(inorder,lrOrder,i+1,iEnd,0,v-1);
    return temp;
}
Node* buildTree(int inorder[], int levelOrder[], int iStart, int iEnd,int n)
{
    //add code here.
    // first node in level order is root
    return findAns(inorder,levelOrder,iStart,iEnd,iStart,iEnd);
}