Recall that the nodes in a binary search tree satisfy the bi

Recall that the nodes in a binary search tree satisfy the binary search tree property: If y is a node in the left subtree of x, then y. key lessthanorequalto x.key. If y is in the right subtree of x, then y. key greaterthanorequalto x. key. Problem 72. Give pseudocode for InorderTreeWalk. PreOrderTreeWalk, and PostOrderTreeWalk. Assuming a balanced tree with n nodes, give a recurrence for the running time of each (they are all the same) and solve your recurrence using the Master Theorem. Problem 73. Execute InorderTreeWalk. PreOrderTreeWalk, and PostOrderTreeWalk on the following operation tree (which is not a binary search tree). Interpret each walk as an arithmetic expression.

Solution

prob 73: inorder traversal: it should be left, node, right.

10-4+3*7

preorder: node, left,right

+-104*37

postorder: left,right,node:

104-37*+

Problem 72: Preorder:

Inorder:

Postorder:

Recurrence will be T(n)=T(n/2) +1, because after 1 comparison, almost half will b left.

Acc to master theorem, T(n)=aT(n/b) +f(n)

hence, T(n)=O(n lg base b a)