Postorder Inorder to Preorder conversion without constructing Binary Tree

Question

I have got given postorder and inorder. My task is to print preorder, but I can't construct a binary tree.

Example: In: POSTORDER 4 2 7 5 9 8 6 3 1 INORDER 4 2 1 5 7 3 6 8 9

Out: 1 2 4 3 5 7 6 8 9

Can anyone help me how to solve this problem?

Answer 1

Got it....

The key observations here to understand are:

1) the last value of post-order array is the root of given tree.

2) To find values that should go to left subtree and the ones to right, find the index where our root (i.e last value in post-order array) lies in inorder array. All values left to that index in inorder array belong to left subtree, All values right to that index belong to right subtree. ok?

So, from above example, root of entire tree is 1. In Inorder array , index of 1 is 2. So, for left subtree:

postorder = [4,2], Inorder = [4,2]

For right subtree: Postorder = [ 7, 5, 9, 8, 6, 3], inorder = [5, 7, 3, 6, 8, 9]

That's it. Recursion would take care of the rest.

My sample code in Pyhton -

post = [4, 2, 7, 5, 9, 8, 6, 3, 1]
inor = [4, 2, 1, 5, 7, 3, 6, 8, 9]

class Node:
    def __init__(self,v):
        self.v = v
        self.l = None
        self.r = None

def build(post,inor):
    assert len(post)==len(inor)
    if not post:
        return None

    root = Node(post[-1])
    if len(post)==1:
        return root

    for i in range(len(inor)): #finding index of root in inorder, in i
        if inor[i] == root.v:
            break

    root.l = build(post[:i],inor[:i]) #both arrays from 0 to index i
    root.r = build(post[i:-1],inor[i+1:]) #post skips last value, which is root
    return root

def pre(r):
    if r==None:return

    print(r.v)
    pre(r.l)
    pre(r.r)

r = build(post,inor)
pre(r)