Generating a binary tree using inorder and preorder traversal

Question

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!

trincot · Accepted Answer · 2021-08-05 13:25:27Z

1

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:

answered Aug 5, 2021 at 13:25

trincot

357k38 gold badges282 silver badges338 bronze badges

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

Collectives™ on Stack Overflow

Generating a binary tree using inorder and preorder traversal

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related