Problem
Define a rank function r (x) for the nodes of any binary tree as follows: If x is the root, then r (x)= 0. If x is the left child of a node y, then r (x)= r (y)-1. If x is the right child of a node y , then r (x)= r (y)+1. Define the credit balance of a tree during a traversal to be the rank of the node being visited. Define the (actual) cost of visiting a vertex to be the number of branches traversed (either going down or up) from the previously visited node. For each of the binary trees. make a table showing the nodes visited, the actual cost, the credit balance, and the amortized cost for an inorder traversal.