Understanding Recursion: Part 3/4

In the previous post, we discussed about how we can deconstruct a programming problem to use recursion to our advantage. We will continue to discuss about programming in this post as well. If you are not prepared to look at code, you may want to skip this post and proceed to the next one in the series. If not, continue reading! Let’s continue to talk about trees then. By now, you understand enough about trees for me to not discuss the basics. If you want a refresher on trees, please read my previous post. In this post, we will look at some common recursive programming problems. You will see the problem and the recursive code to solve it, but not the explanation. We have already discussed how to understand a recursive function in full depth. It’s up to you to understand what’s happening inside these functions here.  

Finding the least common ancestor

Given two nodes in a tree, find the node that is the least common ancestor. Here’s the recursive method to do it:

class node
{
    public:
        int data;
        node* lchild;
        node* rchild;
};

node* leastCommonAncestor(node* root, node* a, node*b)
{
    if(root == NULL)
        return NULL;
    else
    {
        if(root == a || root == b)
            return root;
        else
        {
             node* temp_left = leastCommonAncestor(root->lchild, a, b);
             node* temp_right = leastCommonAncestor(root->rchild, a, b);

        if(temp_left && temp_right)
            return root;
        else
            return temp_left==NULL?temp_right:temp_left;
        }
    }
}

Find the height of a given binary tree

Given a binary tree, find its height. Here, the height corresponds to the maximum height of tree (distance of the root from the furthest leaf node).

int maxdepth(node* root)
{
    if(root == NULL)
        return 0;
    else
    {
        int ldepth = maxdepth(root->lchild);
        int rdepth = maxdepth(root->rchild);
        return(max(ldepth,rdepth)+1);
    }
}

Print all the nodes at a given level

Given a binary tree and a level, print all the nodes that are in that level.

void printLevelNodes(node* root, int cur_level, int level)
{
    if(root == NULL || cur_level>level)
        return;
    else
    {
        if(cur_level == level)
        {
            cout << "%d\n" << root->value << endl;
            return;
        }
        else
        {
            printLevelNodes(root->left, cur_level+1, level);
            printLevelNodes(root->right, cur_level+1, level);
        }
    }
}

Up until now, we looked at recursion from the programmer’s perspective. In the next post, we will discuss about how the machine sees this whole thing. We will see what it does once we make the recursive call.

————————————————————————————————-