[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.


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

  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 ..:)

  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

  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..:)


Post a Comment

Popular posts from this blog