Create postorder from inorder and preorder

Question

I was solving this question - Find PostOrder traversal from Inorder and Preorder traversals of a binary tree. On GeeksForGeeks, I saw the below solution for this:

// A utility function to search x in arr[] of size n 
static int search(int arr[], int x, int n) 
{ 
    for (int i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 

// Prints postorder traversal from given inorder and preorder traversals 
static void printPostOrder(int in1[], int pre[], int n) 
{ 
    // The first element in pre[] is always root, search it in in[] to find left and right subtrees 
    int root = search(in1, pre[0], n); 

    // If left subtree is not empty, print left subtree 
    if (root != 0) 
        printPostOrder(in1, Arrays.copyOfRange(pre, 1, n), root); 

    // If right subtree is not empty, print right subtree 
    if (root != n - 1) 
        printPostOrder(Arrays.copyOfRange(in1, root+1, n), Arrays.copyOfRange(pre, 1+root, n), n - root - 1); 

    // Print root 
    System.out.print( pre[0] + " "); 
}

Now, I know that in postorder, we visits the node after traversing left and right subtrees and that's why, I could deduce from the comments in the printPostOrder() method that firstly something is done with left subtree, then right one and then the node's data is getting printed. I draw some initial recursive calls on paper and it's working fine but I just can't understand how can someone come up with this solution? I'm specially confused in the statement calling the printPostOrder for right subtree. Can anyone please help me to understand what's the logic here behind recursion and how I can understand it by visualizing it properly?

Cătălin Frâncu Cătălin Frâncu · Accepted Answer · 2019-11-20T15:45:09

Let X be the root and let L and R be the left and right subtrees.

    X
  /   \
L      R

Then in[] will look like

+---------+---+-------------------------+
|    L    | X |            R            |
+---------+---+-------------------------+

and pre[] will look like

+---+---------+-------------------------+
| X |    L    |            R            |
+---+---------+-------------------------+

The chunks for L and R will not be identical in in and pre, they will be shuffled, but the key observations are that:

All the elements of L occupy a contiguous chunk in both arrays.
All the elements of R occupy a contiguous chunk in both arrays.
L comes before R in both arrays.

The line int root = search(in1, pre[0], n); finds X at position root in in. Once we have that, we know that:

L has root elements (everything to the left of X in in).
L occurs at position 0 in in and at position 1 in pre.
R has n - root - 1 elements (everything to the right of X in in).
R occurs at position root + 1 in both arrays.

For clarity and consistency, the code could make copies of the proper length and offset:

// If left subtree is not empty, print left subtree 
int lsize = root;
if (lsize != 0) 
  printPostOrder(
    Arrays.copyOfRange(in1, 0, lsize),
    Arrays.copyOfRange(pre, 1, lsize),
    lsize);

// If right subtree is not empty, print right subtree 
int rsize = n - root - 1;
if (rsize != 0) 
  printPostOrder(
    Arrays.copyOfRange(in1, root + 1, rsize),
    Arrays.copyOfRange(pre, root + 1, rsize),
    rsize);

For efficiency, the original code sometimes reuses the same array when the starting offset does not change.

As an aside, this code runs in O(n²) time, but there are faster and more elegant versions in O(n) time.

Create postorder from inorder and preorder

1 Answers