Check if each node of a binary tree has exactly one child

To check if each node of a binary tree has exactly one child

following is the example to Check if each node of a binary tree has exactly one child,

 

Example:

Input:

pre[]={20,10,11,13,12}

Output:

Yes

The given array represents following BST. In the following BST, every internal node has exactly one child. Therefore the output is true.

 

Approach 1:

This approach dimply follows the above idea that all values on right side are either smaller or larger. Use two loops, the outer picks an element one by one, starting from the leftmost element. The inner loops checks if all element on the right side of picked elements are either smaller or greater.

Time Complexity:

O( n² )

where, n is the node of binary tree.

 

 

Approach 2:

1. Find the next preorder successor (or descendant) of the node.
2. Find the last preorder successor (last element in pre[]) of the node.
3. If both successor are less than current node, or both successor are greater than the current node, then continue. Else return false.

 

 

Approach 3:

1. Scan the last two nodes of preorder and mark them as min and max.
2. Scan the every node than the preorder array. Each node must be either smaller than the min node or larger than the max node. update min and max accordingly.

Below is the implementation of the above approach.

 

 

Program in C++ to check binary tree has an only child

#include<iostream.h>
using namespace std;
 
bool hasOnlyOneChild(int pre[], int size)
{
    int nextDiff, lastDiff;
 
    for (int i=0; i<size-1; i++)
    {
        nextDiff = pre[i] - pre[i+1];
        lastDiff = pre[i] - pre[size-1];
        if (nextDiff*lastDiff < 0)
            return false;;
    }
    return true;
}
 
int main() //main method of the program
{
    int pre[] = {8, 3, 5, 7, 6};
    int size = sizeof(pre)/sizeof(pre[0]);
    if (hasOnlyOneChild(pre, size) == true ) 
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

Output:

Yes

the idea is to traverse a tree in inorder traversal and at each step of the traversal check that if the node is having exactly one child. Then append that node into a result array to keep track of such nodes. After the traversal simply print each element of result array.

 

 

 

Program in Java to check binary tree has only child 

class BinaryTree 
{
 
    boolean hasOnlyOneChild(int pre[], int size) 
      {
        int nextDiff, lastDiff;
 
        for (int i = 0; i < size - 1; i++) {
            nextDiff = pre[i] - pre[i + 1];
            lastDiff = pre[i] - pre[size - 1];
            if (nextDiff * lastDiff < 0) {
                return false;
            };
        }
        return true;
    }
 
    public static void main(String[] args) //main method of the program
{
        BinaryTree tree = new BinaryTree();
        int pre[] = new int[]{8, 3, 5, 7, 6};
        int size = pre.length;
        if (tree.hasOnlyOneChild(pre, size) == true)
          {
            System.out.println("Yes");
          } 
       else 
          {
            System.out.println("No");
          }
    }
}

Output:

Yes 

 

 

 

Program in Python to check binary tree has only child 

def hasOnlyOneChild (pre, size):
    nextDiff=0; lastDiff=0
    for i in range(size-1):
        nextDiff = pre[i] - pre[i+1]
        lastDiff = pre[i] - pre[size-1]
        if nextDiff*lastDiff < 0:
            return False
    return True
 
if __name__ == "__main__":  #driver code to access above functions
 
    pre = [8, 3, 5, 7, 6]
    size= len(pre)
 
    if (hasOnlyOneChild(pre,size) == True):
        print("Yes")
    else:
        print("No")

Output:

Yes