treebinary-treeinorderpreorder

Generating a binary tree using inorder and preorder traversal

I want to generate a binary tree using the following inorder/preorder traversal;

Inorder = WOLLONGONG

Preorder = GLOWOLNNGO

This is the tree I came up with:

       G
      /  \
     L    N
    / \  /  \
   O  O  O   G
  /  / \   
 W  L   N

It works for the inorder traversal, but doesn't satisfy the preorder condition. I find it confusing due to the repeated letters.

My guess is that I'm using the wrong "G" as the root?

Thanks in advance!

Solution

  • Indeed, the first G of the preorder happens to correspond here to the last G in the inorder, i.e. the root has no right subtree. This would fit:

             G
        /
       L
      / \
     O   O
    /   / \
   W   L   N
            \
             N
            /
           G
            \
             O