In a perfectly balanced binary tree convert from preorder to inorder

Question

So I have a perfectly balanced (Each node has two children, if it doesn't have any children, it is a leaf node) binary search tree

                  1
          2                  9
       3      6         10       11
     4   5  7   8    12   13  14    15 

and I have that in an array in pre-order

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

now how do I convert my array to in-order or post order ?

Answer 1

well, somehow yesterday I misunderstood your question, or you didn't explain it well. anyway, the thing is that --

you have an array which contains the nodes of a tree, placed in preorder traversal by the tree; now you want to 'reverse-engineer' of it such that you can build or make a tree again from that array so that you can traverse IN or POST order, whatever you required to do!

now one thing you need to understand when you are making the array from the tree, your array should contain the nodes which have value, as well as the nodes which don't have. in another way, you have to place the null nodes of the tree inside of the array, such that you can differentiate the nodes which have value and the nodes which don't have!! pretty simple!

so, what you need to do is, while traversing the tree, you should follow this two-step--

1. if node has value, put it in array

2. else put -1 in array [-1 denotes null value]

now, after traversing the tree and make the array from that tree, you can decode the array to construct back the tree from the array.

PROCEDURE TO MAKE ARRAY FROM TREE

1. DO LEVEL ORDER TRAVERSAL
2. IF ROOT HAS A VALUE, PUT IT IN ARRAY
3. ELSE, PUT -1 IN ARRAY
4. REPEAT, UNTIL ALL NODES, BEEN TRAVERSED

PSEUDOCODE

FUNCTION encode(TREE root, Array a){
  Queue q;
  q->add(root);
  i = 0;
  a[i++] = root->node;

  while(!q){
     TREE temp = q->front();
     q->pop();

     /* if temp's left node contains value */
     if(temp->left){
          a[i++] = temp->left->node;
          q->push(temp->left);
     }else{
       /*  if temp's left node doesn't contains value */
          a[i++] = -1;
     }

     /* do the same for right sub-tree */
     if(temp->right){
          a[i++] = temp->right->node;
          q->push(temp->right);
     }else{
       /*  if temp's left node doesn't contains value */
          a[i++] = -1;
     }
  }
   return a;
}

now you can reverse the algorithm to construct a tree from the array, and after that you can do POST or IN whatever you need!

PROCEDURE TO MAKE TREE FROM ARRAY

1. CREATE ROOT

   1.1 PUT ROOT IN A QUEUE

2. TRAVERSE I-TH INDEX FROM ARRAY

   2.1 IF ARRAY[INDEX] != -1 , CREATE NODE ON LEFT

   2.2 ELSE PUT NULL ON LEFT

3. TRAVERSE I+1-TH INDEX FROM ARRAY

   3.1 IF ARRAY[INDEX] != -1 , CREATE NODE ON RIGHT

   3.2 ELSE PUT NULL ON RIGHT

4. CONTINUE UNTIL QUEUE BECOMES EMPTY

PSEUDOCODE

FUNCTION decode(Array a){
    /* creating root */
    TREE root;
    IF (a[0] == -1) 
         root = createNode(a[0]);
    ELSE
        root = NULL;

    Queue q;
    q->push(root);

    i = 0;

    while(!q){
       TREE temp = q.front();
       q->pop();
       /* if array's index contain value, create node */
       if(a[i+1] != -1){
          temp->left = createNode(a[i+1]);
          q->push(temp->left);
       }else{
          /* else assing null */
          temp->left = NULL;
       }
       /* do the same for right subtree */
       if(a[i+2] != -1){
          temp->right = createNode(a[i+2]);
          q->push(temp->right);
       }else{
          /* else assing null */
          temp->right= NULL;
       }
       i += 2;
    }
}

Now you could able to make a tree from the array you have! and can traverse the tree to get IN or POST order traversal!!

HAPPY FRIDAY : )