data structure programming algorithm

Question

how to draw binary trees whose preorder listing is abcdefgh and whose postorder listing is dcbgfhea.also,list the nodes of binary trees in inorder and level order ?

Answer 1

Tree:

            a
           /  \
          b    e
         /    / \
        c    f   h
       /    / 
      d    g

inorder:

dcbagfeh

Answer 2

Here's a simple Python program that generates all possible inorder listings based on preorder and postorder listings.

from itertools import product

def inorders(pre, pos):
  if not pre: return [""]
  ret = []
  if pre[0] == pos[-1]:
    for left_size in range(len(pre)):
      left = inorders(pre[1:left_size+1], pos[:left_size])
      right = inorders(pre[left_size+1:], pos[left_size:-1])
      for l, r in product(left, right):
        ret.append(l + pre[0] + r)
  return ret

And here's the output for your case:

>>> inorders("abcdefgh", "dcbgfhea")
['bcdafgeh', 'bcdagfeh', 'bdcafgeh', 'bdcagfeh', 'cdbafgeh', 'cdbagfeh', 'dcbafgeh', 'dcbagfeh']