My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called?

int size (BinaryNode t) {
  if (t == null) 
    return 0;
    return 1 + size(t.left) + size(t.right);   
  • $\begingroup$ size returns the number of nodes in t; proof by induction. $\endgroup$ – Raphael Feb 28 '15 at 11:29

Remember that to get the actual value of size(t.left), you have to evaluate the method size at the node t.left, i.e. assuming t.left has left and right children the algorithm with call size((t.left).left) and size((t.left).right).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.