1
$\begingroup$

Draw a BST when you insert, $O,V,E,R,F,L,C,W$ from left-to-right and determine the order of the nodes when using post-order traversal and pre-order traversal.

My attempt at drawing the BST:

             O
           /   \
          E     V
         /  \  / \
        C    F R  W
              \   
               L

post-order traversal I got $C,L,F,E,R,W,V,O$ and for pre-order traversal I got $O,E,C,F,L,V,R,W$

However I'm not 100% sure if what I got both for the drawing of the BST and the traversal's are correct. I was wondering if anyone can check to see if I did this correctly(if my solutions match what you got). I feel that I might of drawn my tree wrong therefore I think that my traversal might be wrong as well.

$\endgroup$
1
  • 1
    $\begingroup$ Seems correct to me $\ddot \smile$ $\endgroup$ – dani_s Mar 2 '14 at 2:50
1
$\begingroup$

Yes, this is correct. The binary tree representation should be straightforward. For the preorder and postorder traversals, I recommend you think about the following pieces of pseudocode:

preorder(node)

if node == null then return

visit(node)

preorder(node.left)

preorder(node.right)

postorder(node)

if node == null then return

postorder(node.left)

postorder(node.right)

visit(node)

The preorder should be fairly straightforward. The postorder is trickier to think about, but only slightly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.