Check if each internal node of a BST has exactly one child

Introduction

Have you ever heard about the Binary Search Trees? Do you want to know how you can check if each internal node has exactly one child?

If yes, then your search for the solution is now over.

This article will help you in writing a program to check if each of the internal nodes of a BST has exactly one child.  

Problem Statement

The problem statement is that we are given a preorder traversal of a Binary Search Tree. Using that information, we have to check if each of the non-leaf or internal nodes has only one child or not. Also, we will assume that all the entries present in the Binary Search Tree are unique.

Sample Input 1

Sample Output:

Dry Run

Preorder traversal places each node's descendants (or Preorder successors) behind the node.

In the example mentioned above, node 19 is the first node in preorder, and all of its descendants follow it. 

All of the children of 19 are smaller than it. 

Every descendant of 9 is greater than it. 

In a BST or Binary Search Tree, we can claim that all descendants of an internal node are either smaller or larger than the node if all internal nodes have just one child. 

Simply said, because the tree is a BST or Binary Search Tree and each node has only one child, all of a node's descendants will either be on the left or right side, i.e., smaller or larger.

Approaches

Approach 1

Simply put, this strategy adheres to the presumption that all values on the right side are either smaller or greater. Use two loops; the outer loop selects each element one at a time, beginning with the element on the left. The inner loop determines if every element to the right of the selected element is smaller or larger. 

This approach has an O(n²) time complexity.

Approach 2

Given that every node's descendants must either be bigger or smaller than the node, For each node in a loop, we can perform the following.
 

1. Locate the node's subsequent preorder successor (or descendant).
    
2. Locate the node's last preorder successor (last element in prebst[]).
    
3. Continue if both successors are less than the current node or both successors are greater than the current node. Return false if not.
    

Implementation in C++:

#include<bits/stdc++.h>
using namespace std;

/* function to check if the internal node of BST has exactly one child */

bool hasOnlyOneChild(int prebst[], int sizebst)
{
	int nextDiffer, lastDiffer;

	for (int i=0; i<sizebst-1; i++)
	{
		nextDiffer = prebst[i] - prebst[i+1];
		lastDiffer = prebst[i] - prebst[sizebst-1];
		if (nextDiffer*lastDiffer < 0)
			return false;;
	}
	return true;
}

int main()
{
	int sizebst;
	cout << "Enter the number of nodes you want in the tree: ";
	cin >> sizebst;
	
	int prebst[sizebst];
	cout << "Enter the nodes of the tree: ";

	for(int i=0; i<sizebst; i++) {
		cin >> prebst[i];
}

	if (hasOnlyOneChild(prebst, sizebst) == true )
		cout<<"Yes...";
	else
		cout<<"No!";
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Implementation in Java

import java.util.*;


class CodingNinjas {
  
    boolean hasOnlyOneChild(int prebst[], int sizebst) {
        int nextDiffer, lastDiffer;
  
        for (int i = 0; i < sizebst - 1; i++) {
            nextDiffer = prebst[i] - prebst[i + 1];
            lastDiffer = prebst[i] - prebst[sizebst - 1];
            if (nextDiffer * lastDiffer < 0) {
                return false;
            };
        }
        return true;
    }
  
    public static void main(String[] args) {
        CodingNinjas bsttree = new CodingNinjas();
        int sizebst;
        Scanner scn = new Scanner(System.in);
        System.out.print("Enter the number of nodes you want in the tree: ");
        sizebst = scn.nextInt();
        
        int prebst[] = new int[sizebst];
        System.out.print("Enter the nodes of the tree: ");


        for(int i=0; i<sizebst; i++) {
            prebst[i] = scn.nextInt();
        }
        
        if (bsttree.hasOnlyOneChild(prebst, sizebst) == true) {
            System.out.println("Yes...");
        } else {
            System.out.println("No!");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Implementation in Python:

def hasOnlyOneChild (prebst, sizebst):
    nextDiffer=0; lastDiffer=0
   
    for i in range(sizebst-1):
        nextDiffer = prebst[i] - prebst[i+1]
        lastDiffer = prebst[i] - prebst[sizebst-1]
        if nextDiffer*lastDiffer < 0:
            return False
    return True
   
if __name__ == "__main__":
  
    prebst = []
    n = int(input("Enter the number of nodes you want in the tree: "))
    print("Enter the nodes of the tree: ",end="")
    for i in range(0, n):
        ele = int(input())
        prebst.append(ele)
    sizebst= len(prebst)
  
    if (hasOnlyOneChild(prebst,sizebst) == True):
        print("Yes...")
    else:
        print("No!")

You can also try this code with Online Python Compiler

Run Code

Output:

Approach 3

1. Scan the final two preorder nodes and mark them as minimum and maximum.
    
2. Go through each node in the preorder array. Each node must be either smaller than the min node or greater than the max node. Update the minimum and maximum values appropriately.
    

Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

/* Function to check if the internal node of BST has exactly one child */
int hasOnlyOneChild(int prebst[], int sizebst)
{	
	/* initialization of maximum and minimum */
	int minimum, maximum;
	if (prebst[sizebst - 1] > prebst[sizebst - 2])
	{
		maximum = prebst[sizebst - 1];
		minimum = prebst[sizebst - 2];
	}
	else
	{
		maximum = prebst[sizebst - 2];
		minimum = prebst[sizebst - 1];
	}

	/* Each element must be either smaller than the minimum 
    or greater than the maximum */
	   
	for(int i = sizebst - 3; i >= 0; i--)
	{
		if (prebst[i] < minimum)
			minimum = prebst[i];
		else if (prebst[i] > maximum)
			maximum = prebst[i];
		else
			return false;
	}
	return true;
}

int main()
{
	int sizebst;
	cout << "Enter the number of nodes you want in the tree: ";
	cin >> sizebst;
	
	int prebst[sizebst];
	cout << "Enter the nodes of the tree: ";

for(int i=0; i<sizebst; i++) {
cin >> prebst[i];
}

	if (hasOnlyOneChild(prebst,sizebst))
		cout <<"Yes...";
	else
		cout <<"No!";
		
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Implementation in Java

import java.util.*;

class CodingNinjas {
  
    boolean hasOnlyOneChild(int prebst[], int sizebst) {
     
        int minimum, maximum;
        if (prebst[sizebst - 1] > prebst[sizebst - 2]) {
            maximum = prebst[sizebst - 1];
            minimum = prebst[sizebst - 2];
        } else {
            maximum = prebst[sizebst - 2];
            minimum = prebst[sizebst - 1];
        }
  
        /* Every element must be either smaller than minimum 
           or greater than maximum */
        for(int i = sizebst - 3; i >= 0; i--) {
            if (prebst[i] < minimum) {
                minimum = prebst[i];
            } else if (prebst[i] > maximum) {
                maximum = prebst[i];
            } else {
                return false;
            }
        }
        return true;
    }
  
    public static void main(String[] args) {
        CodingNinjas bsttree = new CodingNinjas();
        int sizebst;
        Scanner scn = new Scanner(System.in);
        sizebst = scn.nextInt();
        
        int prebst[] = new int[sizebst];
        
        for(int i=0; i<sizebst; i++) {
            prebst[i] = scn.nextInt();
        }
        
        if (bsttree.hasOnlyOneChild(prebst, sizebst) == true) {
            System.out.println("Yes...");
        } else {
            System.out.println("No!");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Implementation in Python

def hasOnlyOneChild(prebst,sizebst):

	minimum=0; maximum=0

	if prebst[sizebst-1] > prebst[sizebst-2] :
		maximum = prebst[sizebst-1]
		minimum = prebst[sizebst-2]
	else :
		maximum = prebst[sizebst-2]
		minimum = prebst[sizebst-1]

	for i in range(sizebst-3, 0, -1):
		if prebst[i] < minimum:
			minimum = prebst[i]
		elif prebst[i] > maximum:
			maximum = prebst[i]
		else:
			return False
	return True

if __name__ == "__main__":
    prebst = []
    sizebst = int(input("Enter the number of nodes you want in the tree: "))
    print("Enter the nodes of the tree: ")
    for i in range(0, sizebst):
        ele = int(input())
        prebst.append(ele)
      
    if (hasOnlyOneChild(prebst,sizebst) == True):
        print("Yes...")
    else:
        print("No!")

You can also try this code with Online Python Compiler

Run Code

Output: