in Binary Tree ,checking if given node is leaf node or not

Question

I have written the code to find if the given node is leaf node or not , It works fine for positive case , i.e. when the entered node is a leaf node , the code code traverse till the node and and if it is leaf node , gives the output and stops , but the negative scenario is failing when the entered node is not a leaf node, The code keeps traversing the complete tree even when it has passed through the node and it is not a leaf node.

boolean isLeaf(BTNode node, int data) {
   if (node == null) {
    return false;
   }
System.out.println("Node traversed :"+ node.data);
if (node.left == null && node.right == null && node.data == data) {
    System.out.println("Node : " + node.data + " is leaf node");
    return true;
}
return (isLeaf(node.left, data) || isLeaf(node.right, data));
}

Can any one tell what is the condition to stop the recursion if the node is found and it is not a leaf node.

Thanks.

Solution 1

Try something like this:

boolean isLeaf(BTNode node, int data) {
    if (node == null)       
        return false;
    if (node.left == null && node.right == null)      
        return true; 
    isLeaf(node.left); 
    isLeaf(node.right);      
}

The main problem with the way you implemented it is the line:

return (isLeaf(node.left, data) || isLeaf(node.right, data));

Did you think of what happens when you execute it actually?

Edit: If you just want to check if a node is a leaf do:

boolean isLeaf(BTNode node, int data) {
    if (node == null)
        return false;    
    if (node.right == null && node.left == null)
        return true;
    return false; 
}

Solution 2

That's because your code includes traversal for no obvious reason. Think about what this recursive call does - return (isLeaf(node.left, data) || isLeaf(node.right, data)); . That should most likely be return false

Solution 3

bool isleaf(Node* root)
    {
        if(root->left==NULL && root->right==NULL) return true;
        else return false;
    }