0

I am working through the book "Cracking the coding interview" by Gayle McDowell and came across an interesting recursive algorithm that sums the values of all the nodes in a balanced binary search tree.

int sum(Node node) {
 if (node == null) {
  return 0;
 }
 return sum(node.left) + node.value + sum(node.right);
}

Now Gayle says the runtime is O(N) which I find confusing as I don't see how this algorithm will ever terminate. For a given node, when node.left is passed to sum in the first call, and then node.right is consequently passed to sum in the second call, isn't the algorithm computing sum(node) for the second time around? Wouldn't this process go on forever? I'm still new to recursive algorithms so it might just not be very intuitive yet.

Cheers!

Improve this question
1
  • node.left is the left child of node, node.right is the right child. sum(node) recursively computes the sum of the left child, then the right child and adds them together (with node's value) Commented Oct 19, 2016 at 19:40

2 Answers 2

Reset to default
1

The process won't go on forever. The data structure in question is a Balanced Binary Search Tree and not a Graph which can contain cycles.

Starting from root, all the nodes will be explored in the manner - left -> itself -> right, like a Depth First Search.

node.left will explore the left subtree of a node and node.right will explore the right subtree of the same node. Both subtrees have nothing intersecting. Draw the trail of program control to see the order in which the nodes are explored and also to see that there is no overlapping in the traversal.

Since each node will be visited only once and the recursion will start unwinding when a leaf node will be hit, the running time will be O(N), N being the number of nodes.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Ah! So node.right and node.left are actually children of node! That makes soo much more sense! I see now why you can't have cyclic behaviour in the recursive calls. Thanks!
0

The key to understanding a recursive algorithm is to trust that it does what it is deemed to. Let me explain.

First admit that the function sum(node) returns the sum of the values of all nodes of the subtree rooted at node.

Then the code

 if (node == null) {
  return 0;
 }
 return sum(node.left) + node.value + sum(node.right);

can do two things:

  1. if node is null, return 0; this is a non-recursive case and the returned value is trivially correct;

  2. otherwise, the fuction computes the sum for the left subtree plus the value at node plus the sum for the right subtree, i.e. the sum for the subtree rooted at node.

So in a way, if the function is correct, then it is correct :) Actually the argument isn't circular thanks to the non-recursive case, which is also correct.

We can use the same way of reasoning to prove the running time of the algorithm.

Assume that the time required to process the tree rooted at node is proportional to the size of this subtree, let |T|. This is another act of faith.

Then if node is null, the time is constant, let 1 unit. And if node isn't null, the time is |L| + 1 + |R| units, which is precisely |T|. So if the time to sum a subtree is proportional to the size of the subtree, the time to sum a tree is prortional to the size of the tree!

Improve this answer

1 Comment

I don't agree with the downvote, this was a very nice explanation. When my "reputation" reaches 15, i'll be back to upvote!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.