| 36|

parent 36 L|7| R |47|

parent 7 L|4| R |9|

parent 4 L |2|

parent 2 R |3|

Analyze the execution of the algorithm foo() when it is applied to the above tree with the root node 36 as initial input. What value does foo return? What attribute of the tree does foo measure?

Node class used by algorithm

class TreeNode {

int data;

TreeNode left;

TreeNode right;

}

Method to return the maximum of two ints

public static int max (int a, int b) {

if (a < b) {

return b;

}

else {

return a;

}

}

Mystery algorithm

public static int foo(TreeNode node) {

if (node == null) {

return 0;

}

else {

return 1 + max(foo(node.left), foo(node.right));

}

}

Initial call in main assume above tree and root is pointing to node 36

int answer = foo(root);

----------------------------------------------------------------------------------------------------------------------------------

foo(root) returns ___________

What attribute of the tree does foo() measure? ___________________________________