How can I return leaf nodes randomly in a BST?

Question

---

I want to get one of the leaf nodes as an output(just one of them).But not the same leaf node for everytime...I want to get a different leaf node for everytime with the help of "srand" function...I tried to solve this problem using array but could not be successfull.Then I decided to go on with a different algorithm with the help of a friend who commented on this post...
I am generating a random integer if it is odd I go on with the left child ,vice versa... But get the same node as an output can not solve the problem...

void LeafNodesRandomly(BST*p)
{
int i;
srand(time(NULL));
i=rand()%2;//Generating a random int for determining to go right or left of a current node
//printf("%d\t",i);

while(p->left !=NULL || p->right !=NULL)
{
    if(p->left==NULL && p->right!=NULL)//Just have a right child
    {
        p=p->right;
        if(p->left==NULL && p->right==NULL)//If the right child is a leaf node print and break
        {
            printf("%d\t",p->data);
            break;
        }
    }

    if(p->left!=NULL && p->right==NULL)//Just have a left child
    {
        p=p->left;
        if(p->left==NULL && p->right==NULL)//If the left child is a leaf node print and break
        {
            printf("%d\t",p->data);
            break;
        }
    }

    if(p->left!=NULL && p->right!=NULL)// The current node have two children
    {
        if(i==0)
        {
            p=p->left;
            if(p->left==NULL && p->right==NULL)// If the randomly generated int is "0" go left child and if the left child is a leaf node print and break
            {
                printf("%d\t",p->data);
                break;
            }
        }

        if(i==1)
        {
            p=p->right;
            if(p->left==NULL && p->right==NULL)// If the randomly generated int is "1" go right child and if the right child is a leaf node print and break
            {
                printf("%d\t",p->data);
                break;
            }
        }
    }



 /*if(i==0) // If you open this if and else block you can randomly reach some of other leafs!!!
    {
        i=i+1;
    }
    else
        i=i-1;
    } */
    }

}

---

This is my main function:

I have 13 or NULL as an output

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#include "bst.h"

int main()
{
    BST*root=NULL;

    root=AddNode(root,9);
    root=AddNode(root,11);
    root=AddNode(root,7);
    root=AddNode(root,13);
    root=AddNode(root,10);
    root=AddNode(root,5);
    root=AddNode(root,6);
    root=AddNode(root,8);

   LeafNodesRandomly(root);
}

Answer 1

You can simplify your code quite a bit by making use of information you already know. For example, the first few lines of your loop are:

while(p->left !=NULL || p->right !=NULL)
{
    if(p->left==NULL && p->right!=NULL)//Just have a right child
    {
        p=p->right;
        if(p->left==NULL && p->right==NULL)//If the right child is a leaf node print and break
        {
            printf("%d\t",p->data);
            break;
        }
    }

When you enter the loop, you know that, at most, one of the child pointers is null. So you know that if p->left == NULL, p->right cannot be null. Otherwise you never would have entered the loop body. And because the loop body won't be entered if both child pointers are null (i.e. p points to a leaf node), there's no reason to check for a leaf node after assigning a pointer. The while condition will exit the loop as appropriate, p will be pointing to a leaf node, and you can print the data.

In addition, you can increase the variability of which leaf node you get by picking a new random number whenever you get to a node that has two children.

The resulting code is much shorter and simpler. It reduces duplicated code and eliminates redundant logic checks.

void LeafNodesRandomly(BST*p)
{
    // Seed the random number generator.
    srand(time(NULL));

    // Randomly select a leaf node
    while(p->left !=NULL || p->right !=NULL)
    {
        if(p->left==NULL)//Just have a right child
        {
            p=p->right;
        }
        else if(p->right==NULL)//Just have a left child
        {
            p=p->left;
        }
        else // The current node have two children
        {
            // Randomly select a child node.
            int i = rand()%2;
            if(i==0)
            {
                p=p->left;
            }
            else
            {
                p = p->right;
            }     
        }
    }
    // When you get here, p is pointing to a leaf node.
    printf("%d\t",p->data);
}

The "randomly select a child node" can be further condensed by using the ternary operator:

// Randomly select a child node.
p = (rand()%2) == 0 ? p->left : p->right;

(Yes, nitpickers, I know that the == 0 is not actually necessary. It is more clear, though, especially to less experienced programmers. No need to tell me that a kitten dies every time somebody writes == 0.)