Originally Posted by

**RyanC**
lets say I have fully tree with node X yeah? I call a function by node X so the root is X .. yup? that's fine!!!

in another time I called one of the child of node X lets say it's y, so if I call a function with node y, the new root is y, my question why "y" called new root?! I mean how does the PC know now I've new root? and how he's assign it as root and not a node?!

Let's consider a concrete example: a binary tree denoted by a pointer to its root node, and a simple recursive function for computing the height of the binary tree:

Code:

struct node
{
struct node *left;
struct node *right;
};
size_t compute_height(struct node *root)
{
if (!root)
{
return 0;
}
size_t left_subtree_height = compute_height(root->left);
size_t right_subtree_height = compute_height(root->right);
return 1 + ((left_subtree_height > right_subtree_height) ? left_subtree_height : right_subtree_height);
}

So, we see that in the compute_height function, the root parameter is initially called with the root of the overall tree. But wait, if the tree is not empty, we call compute_height(root->left). In this recursive call, the compute_height function's argument is root->left, which means that the parameter root in this recursive call corresponds to the argument root->left, i.e., from the perspective of this recursive function call, root->left is the root of the tree. This tree is actually a subtree, but from the perspective of the recursive function call, it might as well be the overall tree.

That's the key to recursive thinking here: a subtree is a tree, so whatever can be done with a tree, can be done with a subtree. A tree has a root; a subtree has a root. What's the height of a binary tree? 0 if the tree is empty, otherwise it's 1 + the height of the taller of its two subtrees. How do we compute the height of the subtrees? They are trees, so recursively apply this function to compute the height of a tree, i.e., for one recursive call, the root is the root of the left subtree, and for the other recursive call, the root is the root of the right subtree.