[Amazon]construct tree with preorder traversal

Leaves are represented with L and non-leaf with N in a tree. Each node has either 0 or 2 children. so if given preorder traversal of this tree, construct the tree.

Comments

  1. but the tree wont be unique...we can have many such trees...pls elaborate..

    ReplyDelete
  2. @Anonymous no since each node in the tree has either 0 or 2 nodes ,so preorder traversal will always be unique..please check this taking some example ..:)

    ReplyDelete
  3. eg.
    consider the preorder 1 2 4 5 6 7 3

    Tree 1:

    2,3 are child of 1
    4,7 are child of 2
    5,6 are child of 4

    Tree 2:

    2,3 are child of 1
    4,5 are child of 2
    6,7 are child of 5

    ReplyDelete
  4. @Anonymous in your example 5 is leaf node in tree 1 so it will be representd in above tree as L and in second tree it is non leaf so it will be represented as N(Non-leaf).so they are not same..:)

    ReplyDelete

Post a Comment

Popular posts from this blog

Circular game survival