BST Traversal
Draw the Binary Search Tree (BST) we would get if we were to insert the letters C O M P U T E R S in the order listed (i.e., C is the first letter added to the tree).
Given that BST, what would be the order of the nodes visited in:
- A pre-order traversal
- A post-order traversal
- An in-order traversal
Try again
Repeat Question 1, but with the letters S R E T U P M O C
And the other way
Draw a binary tree1 that would produce the following results:
- order of nodes visited in a pre-order traversal is: M,C,O,E,U,P,T,S,R
- order of nodes visited in a post-order traversal is: O,C,P,T,U,R,S,E,M
- order of nodes visited in an in-order traversal is: C,O,M,P,U,T,E,R,S
What to hand in
You must submit a file called ex3.txt with the answers to questions 1 and 2 in the following format:
1.1 C,O,M,P,U,T,E,R,S 1.2 S,R,E,T,U,P,M,O,C 1.3 H,I,A,N,N,A,A,N,D,B,R,I,A,N 2.1 A,B,C,D,E,F,G 2.2 T,H,E,S,E,A,R,E,N,O,T,T,H,E,C,O,R,R,E,C,T,A,N,S,W,E,R,S 2.3 H,E,L,L,O,W,O,R,L,D
That is, questions 1.1 - 2.3 each on their own line, starting with the question number and ending with the traversal number. One space between the question number and the traversal, no other spaces.
You do not need to submit a solution for question 3 (though you should try it).