Question

There are generally considered to be four distinct binary tree traversals: preorder, inorder, postorder and level-order. Consider the following questions about these different kinds of traversals. Answer one of them that has not already been answered.

• What is the result of the various tree traversals when performed on an arithmetic expression tree?
• Which of the traversals are depth-first? Which are breadth-first?
• Which kind of traversal of a binary search tree produces the values in sorted order?
• Which of the traversals lend themselves to recursive solutions? Why are those solutions much simpler than their iterative counterparts?
• Provide the outline of the algorithm for a level-order traversal.

Choose one type of tree traversal and give an example of a situation, in which it would be useful.

Answer 1

attached detailed solution question 6 i did not give solution because so many question in single assignment .

i can answer atmost 4 if there are many.
Solhi - Angry preorder post order, Phorder, level order on anthmatic expremion if they are traversed Result see example: a preorder, Root, left, Right ft abaca so its pretis Notation of anithmatic Notation. Posl order: left, right, woot its post fix Notation a bt cd - * of anithmatic marborkorteio ene prenion, gives infix indarder; left, Roof, right atb * .c-d Notation of anthmatic notation. level order! * + ab ed some non-meaning you value as result can be said all the operator one side which is left f operand on other side, seprate operands & operator · will be Ansa-2 horder, preorder, post orders are Depth first traversal since it will go till reag in each iteration: for each node Breath first traversal is level order vice-versa since all Nodes are traversed leven while le a node then all its child repeat Pn order traversal in 85t gives sorted away. CS And:3 Scanned with CamScanner

014; - Any of above can lend them.selves to secursivesolu. whenever there is a case of repeated deteta junction Call of same value. Phistead of going for recursion stored the oth value & can reme it that is Called Dynamic programming. 0:5 level order on BFT we can Algo 0 Tolololo e b es ferke An amay named waited index as Node values put initially visited assay in all field o. Tolo C व fg fake a' queue, insent foot of the tree in queue. 4 Marks it's visited as to now start. BFTCV) visited (V)=1; add CV, 0); while (& not empty) x= delete queue (Q); Pf(x); forfall wadjecent to a) if (w is not visited) visited (LW) = add cw, 0); is ey g. , La Oh 0:6! BFT level order can be ened for MST creation if all Nodes have same weights. CS Scanned with CamScanner