Binary tree Inorder traversal from only postorder traversal provided

Question

I got a question in my coding challenge.

A complete binary tree is a binary tree where every node except the leaf node has two child nodes and the last level of the tree for an edge-height h has 2^h leaf-nodes.

Your task is simple, given the post-order traversal for a complete binary tree, print its in-order traversal.

The elements in the binary tree are of type character i.e. each node stores one character value.

---

Format of input / output

Input Format:

Only one string input denoting the postorder traversal.

Constraints:

1 <= input.length <= 1000

Output Format:

output one string that denotes the inorder traversal of the binary tree

---

Sample

Sample Input 0:

BCA

Sample Output 0:

BAC

Answer 1

I did have a full answer ready to go, but @EricWang beat me to the implementation. So here's a supplementary answer describing the process in more detail. Please accept his as the answer.

---

I'm going to use the post-order traversal DEBFGCA, as it's useful to consider slightly more nodes.

Because the tree is complete, for any given node we know that the the number of children on the left is the same as the number of children on the right. Therefore we can look at the post-order traversal DEBFGCA and know that it has the structure LLLRRRN, where L is the post-order traversal of the left subtree, R is the post-order traversal of the right subtree, and N is the node itself.

More generally, we know that the post-order traversal of the left subtree is characters 0 to (tree.length - 1)/2 - 1, and the post-order traversal of the right subtree is characters (tree.length -1)/2 - 1 to tree.length - 2. The node is the last character, at tree.length - 1.

Obviously, to change this to an in-order traversal, we just have to identify the left and right subtrees, change them to in-order traversal, and then return LLLNRRR. We can use recursion to convert the left and right subtrees to in-order.

So for example, start with DEBFGCA. We know the structure is LLLRRRN, so the left subtree is DEB, the right subtree is FGC, and the node is A. We want to turn DEB into in-order...

Process DEB. We know the left subtree is D, right is E, node is B. Both subtrees have length 1, so are leaves. No further recursion required. Return LNR, which is DBE.

Process FGC. As before, return FCG.

Now we know the in-order left is DBE and right is FCG. Return LLLNRRR, which is DBEAFCG.

Answer 2

You can do it dynamically, with recursion.

---

Mechanism

• Split a tree to 3 parts: left, right, root.
• Re-join them in order: left, root, right.
• Split recursively, till the length of subtree is one.

---

Code - in Java

PostToInOrder.java

public class PostToInOrder {
    public static String convert(String post) {
        checkPerfect(post); // check whether tree is perfect,

        return convertInner(post);
    }

    private static String convertInner(String post) {
        int len = post.length();
        if (len == 1) return post; // base case,

        String left = post.substring(0, len >> 1); // left of post,
        String right = post.substring(len >> 1, len - 1); // right of post,
        char root = post.charAt(len - 1); // root of post,

        return convertInner(left) + root + convertInner(right);
    }

    private static void checkPerfect(String tree) {
        if (!isPerfect(tree)) throw new IllegalArgumentException("input is not perfect tree, size: " + tree.length());
    }

    private static boolean isPerfect(String tree) {
        int len = tree.length();
        if (len < 1) return false;

        while (len != 0) {
            if ((len & 1) == 0) return false;
            len >>= 1;
        }

        return true;
    }
}

PostToInOrderTest.java:
(Unit test, via TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

public class PostToInOrderTest {
    @Test
    public void test() {
        Assert.assertEquals(PostToInOrder.convert("BCA"), "BAC");
        Assert.assertEquals(PostToInOrder.convert("02146538A9CEDB7"), "0123456789ABCDE");

        Assert.assertEquals(PostToInOrder.convert("A"), "A"); // single element,
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void test_invalid_empty() {
        PostToInOrder.convert("");
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void test_invalid_notPerfect() {
        PostToInOrder.convert("AB");
    }
}

---

BTW:

• The tree described in question is a perfect binary tree.
  It's a sub type of complete binary tree.
  A complete tree is not necessary perfect, its last level could lack of some leaves.
  e.g AB is a complete tree, but not perfect tree.