Binary Tree problem

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • APEJMAN
    New Member
    • Feb 2008
    • 33

    Binary Tree problem

    Hi, would you please guide me with this question?
    suppose we have a tree with at least 3 nodes containing unique integer values. I want to draw an example tree that justifies my answer and write out the traversals.
    of if this is not possible, would you please explain me the logic for why such a tree is impossible.

    1.) Is it possible for the pre-order and in-order traversals to be the same?
    2.) Is it possible for the post-order and in-order traversals to be the same?
    3.) Is it possible for the post-order and pre-order traversals to be the same?

    Thanks
  • Ganon11
    Recognized Expert Specialist
    • Oct 2006
    • 3651

    #2
    Draw a small tree (3 nodes) with unique values and write down the pre-, post-, and in-order traversals. See if they are ever the same. Try with a few examples and see if they are ever the same.

    Comment

    • JosAH
      Recognized Expert MVP
      • Mar 2007
      • 11453

      #3
      If your little tree is a degenerate little list (e.g. no left sub-trees) then the preorder
      traversal is identical to the inorder traversal). A similar reasoning applies to a
      left degenerate tree (no right sub-trees)

      kind regards,

      Jos

      Comment

      Working...