Can anybody explain exactly how this recursion works? We calculate the size of the left sub tree and the right sub tree, but what about the nodes that are on the right side (i.e, right child) of the left sub tree? Also, why do we add the 1 everytime we call it?
int size(struct node* node) // We pass root { if (node==NULL) return 0; else return(size(node->left) + 1 + size(node->right)); } This is how the recursion works.
int size(struct node* node) // We pass root { if (node==NULL) return 0; //if the current node is null return a 0 so no add 1 is done else return(size(node->left) + 1 + size(node->right)); } lets split up the return statement
return
size(node->left) recursive call to the left node of the current node
+1 for the current node
size(node->right) recursive call to the right node of the current node
by the time the recursion is done it will return the current size of the whole tree
if we start at the head of the tree it will call the left sub tree recursively until it hits a null, returns 0 for that node so no add 1 is done for it, then goes back up 1 level calls the right sub tree of last node not null and keeps going until the whole tree is done, adding 1 for each and only each node that is not null.
example
5 3 8 1 4 7 9 is the tree
the recursion starts at 5
it has both a left and right subtree
the left is called first 3 three has a left and right subtree left first so it goes to 1. 1 has no subtree but 1 is not null so it calls the left subtree which returns 0
0 + 1 + 0 is the 1 node return which is 1.
it then goes back up to 3
3 has a right subtree so it calls that
4 has no subtree so again its return will be 0 + 1 + 0
now back to 3 its return will be 1 + 1 + 1
now back to 5 so the return from the 3 node will be 3
so right now in the recursion it will be 3 + 1 + size->right
it will recursively return the right subtree so the return will be
3 + 1 + 3 which is 7 nodes not null
Every binary tree has a root. The root can be null, in which case this tree is empty and has size 0. Otherwise, there's at least one vertex (the root) plus however many vertices are contained in any subtrees hanging from the root. This leads to two scenarios for calculating the size:
[the size of the left subtree] + [the size of the right subtree] + 1 (for the root vertex itself).You need to recognize at this point that a subtree is itself a tree. You also will need to take the "recursive leap of faith" that size() is a function that returns the size of a tree, without worrying about how it manages to do so. If you can accept that as a fact, it should suddenly become obvious that the second case outlined above can be calculated by invoking the size() function on the left subtree, invoking it on the right subtree, summing the results, and adding 1 for the current (sub)tree's root! For both left and right, if there is no subtree the returned contribution will be zero. Otherwise, trust the function to hand back the size of that subtree and use the results to calculate the current (sub)tree's size which you, in turn, hand back to whoever invoked you via the return statement.