Binary Search Tree Traversals

Question

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.

Answer 1

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.