Question

(4 marks) Consider the binary tree shown in Figure 8. Perform the iterative pre-order tree traversal using a stack as shown to you in class. Write your answers in the U- shaped diagrams in Figure 9. For the first stack, show the value on the stack before entering the loop. For the rest of the stacks, show the values on the stack at the end of each loop iteration. 42 3 67 19 19 35 12 29 55 60 54 Figure 8 Visited nodes:

Answer 1

Page NO. Date: Solution STEPS TO BE FOLLOWED : create an empty stack and push root node to stack 42 S → so while stack is not empty → pop an item from stack & prine it lush right chied of popped item to stack if it exuts qush left child of popped item to stack if it exista o/P : 42 4.0/1: 42 3 12 19 3 07 29 67 S 2 O/ 42 3 & Oll: 42 3 19 29 67 S 19 67 6. Off: 1:42 3 19 12 29 67 S O/P: 42 3 19 19 35 S 12 29 64 S

Page No. Date: 012! 42 3 12 29 67 19 55 60 85 es 8.0/P: 42 3 191 12 29 67 19 55 60 35 es 9. 01P 42 3 19 12 29 67 19 55 60 | 35 10.0/8 42 3 19 29 67 19 55 40 35 54 S 1. OPP: 42 3 19 12 67 55 60 35 7 stack is emply stop S 60 35 67 1955 29 54 Proder 42 3 19 travesai

For the first stack, the value on the stack before entering the loop is the root which is 42 and for the rest of the stacks, iteration wise values have been shown. The visited if needed, because it is not asked in the question, for each iteration will be all the nodes that had been pushed into the stack till that iteration(include the nodes which have been popped too because they were also pushed into the stack once)