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 ?

Preorder and postorder are ways to traverse a tree. You still have the same underlying tree, you just traverse it differently. See: Tree traversal on wikipedia — NullUserException
– NullUserException, Commented Sep 26, 2010 at 17:46

Mazyod · Accepted Answer · 2011-06-03 14:48:11Z

4

Tree:

inorder:

dcbagfeh

level order (i.e BFS):

abecfhdg

edited Jun 3, 2011 at 14:48

answered Sep 26, 2010 at 17:38

Mazyod

22.6k10 gold badges97 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sheldon L. Cooper · Accepted Answer · 2010-09-27 00:42:18Z

0

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']

edited Sep 27, 2010 at 0:42

answered Sep 26, 2010 at 23:34

Sheldon L. Cooper

3,27021 silver badges13 bronze badges

2 Comments

aaronasterling Over a year ago

since you don't ever use n, you can just replace the first two lines of inorder with if not pre: return ['']

Sheldon L. Cooper Over a year ago

@AaronMcSmooth - I used n twice, but I made the change anyways. Thanks.

Collectives™ on Stack Overflow

data structure programming algorithm

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related