Wednesday, May 11, 2011

Nth node in inorder traversal

Problem

Here we have to return pointer to nth node in the inorder traversal

Solution

// Get the pointer to the nth inorder node in "nthnode"
void nthinorder(node *root, int n, mynode **nthnode)
{
static whichnode;
static found;

if(!found)
{
if(root)
{
nthinorder(root->left, n , nthnode);
if(++whichnode == n)
{
printf("\nFound %dth node\n", n);
found = 1;
*nthnode = root; // Store the pointer to the nth node.
}
nthinorder(root->right, n , nthnode);
}
}
}
17. Level order traversal
18. Number of leaves
int count_leaf(node *root)
{
if(node == NULL) return 0;
if (node->left == NULL && node->right == NULL) //it is a leaf
return 1;
else
return (count_leaf(node->left) + count_leaf(node->right)) ;


}

0 comments:

Post a Comment