Check if each node of a binary tree has exactly one child
Given a binary tree, check if each node has exactly one child or not. In other words, check whether the binary tree is skewed or not.
For example, the following binary tree is also skewed:
The idea is simple. If the binary tree’s height is equal to the total number of nodes in the tree, then the binary tree is skewed. Otherwise, the binary tree cannot be skewed. Following is the implementation in C++, Java, and Python based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Recursive function to calculate the size of a binary tree int getSize(Node* root) { // Base case: empty tree has size 0 if (root == nullptr) { return 0; } // recur for the left and right subtree return 1 + getSize(root->left) + getSize(root->right); } // Recursive function to calculate the height of a binary tree int findHeight(Node* root) { // Base case: an empty tree has a height of 0 if (root == nullptr) { return 0; } // recur for the left and right subtree and consider the maximum depth return 1 + max(findHeight(root->left), findHeight(root->right)); } // Function to check if each node of a binary tree has exactly one child bool isSkewedTree(Node* root) { return getSize(root) == findHeight(root); } int main() { Node* root = new Node(15); root->right = new Node(30); root->right->left = new Node(25); root->right->left->left = new Node(18); root->right->left->left->right = new Node(20); bool isSkewed = isSkewedTree(root); if (isSkewed) { cout << "The binary tree is skewed"; } else { cout << "The binary tree is not skewed"; } return 0; } |
Output:
The binary tree is skewed
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// Data structure to store a binary tree node class Node { int key; Node left, right; Node(int key) { this.key = key; this.left = this.right = null; } } class Main { // Recursive function to calculate the size of a binary tree public static int getSize(Node root) { // Base case: empty tree has size 0 if (root == null) { return 0; } // recur for the left and right subtree return 1 + getSize(root.left) + getSize(root.right); } // Recursive function to calculate the height of a binary tree public static int findHeight(Node root) { // Base case: an empty tree has a height of 0 if (root == null) { return 0; } // recur for the left and right subtree and consider the maximum depth return 1 + Integer.max(findHeight(root.left), findHeight(root.right)); } // Function to check if each node of a binary tree has exactly one child public static boolean isSkewedTree(Node root) { return getSize(root) == findHeight(root); } public static void main(String[] args) { Node root = new Node(15); root.right = new Node(30); root.right.left = new Node(25); root.right.left.left = new Node(18); root.right.left.left.right = new Node(20); boolean isSkewed = isSkewedTree(root); if (isSkewed) { System.out.println("The binary tree is skewed"); } else { System.out.println("The binary tree is not skewed"); } } } |
Output:
The binary tree is skewed
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to calculate the size of a binary tree def getSize(root): # Base case: empty tree has size 0 if root is None: return 0 # recur for the left and right subtree return 1 + getSize(root.left) + getSize(root.right) # Recursive function to calculate the height of a binary tree def findHeight(root): # Base case: an empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider the maximum depth return 1 + max(findHeight(root.left), findHeight(root.right)) # Function to check if each node of a binary tree has exactly one child def isSkewedTree(root): return getSize(root) == findHeight(root) if __name__ == '__main__': root = Node(15) root.right = Node(30) root.right.left = Node(25) root.right.left.left = Node(18) root.right.left.left.right = Node(20) if isSkewedTree(root): print('The binary tree is skewed') else: print('The binary tree is not skewed') |
Output:
The binary tree is skewed
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. However, it does two traversals of the binary tree – one to calculate its size and another to calculate its height. We can improve the above solution by calculating the height and the size in a single traversal tree, as demonstrated below.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Recursive function to return the height of a binary tree. // It also calculates the tree size and stores it in the reference variable `size` int findHeight(Node* root, int &size) { // Base case: an empty tree has a height of 0 if (root == nullptr) { return 0; } size++; // recur for the left and right subtree and consider the maximum depth return 1 + max(findHeight(root->left, size), findHeight(root->right, size)); } // Function to check if each node of a binary tree has exactly one child bool isSkewedTree(Node* root) { int size = 0; int height = findHeight(root, size); return height == size; } int main() { Node* root = new Node(15); root->right = new Node(30); root->right->left = new Node(25); root->right->left->left = new Node(18); root->right->left->left->right = new Node(20); bool isSkewed = isSkewedTree(root); if (isSkewed) { cout << "The binary tree is skewed"; } else { cout << "The binary tree is not skewed"; } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
import java.util.concurrent.atomic.AtomicInteger; // Data structure to store a binary tree node class Node { int key; Node left, right; Node(int key) { this.key = key; this.left = this.right = null; } } class Main { // Recursive function to return the height of a binary tree. // It also calculates the tree size and stores it in variable `size` public static int findHeight(Node root, AtomicInteger size) { // Base case: an empty tree has a height of 0 if (root == null) { return 0; } size.incrementAndGet(); // recur for the left and right subtree and consider the maximum depth return 1 + Integer.max(findHeight(root.left, size), findHeight(root.right, size)); } // Function to check if each node of a binary tree has exactly one child public static boolean isSkewedTree(Node root) { AtomicInteger size = new AtomicInteger(0); int height = findHeight(root, size); return height == size.get(); } public static void main(String[] args) { Node root = new Node(15); root.right = new Node(30); root.right.left = new Node(25); root.right.left.left = new Node(18); root.right.left.left.right = new Node(20); boolean isSkewed = isSkewedTree(root); if (isSkewed) { System.out.println("The binary tree is skewed"); } else { System.out.println("The binary tree is not skewed"); } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to return the height of a binary tree. # It also calculates the tree size and stores it in `size` def findHeight(root, size=0): # Base case: an empty tree has a height of 0 if root is None: return 0, size size += 1 left, size = findHeight(root.left, size) right, size = findHeight(root.right, size) # recur for the left and right subtree and consider the maximum depth return 1 + max(left, right), size # Function to check if each node of a binary tree has exactly one child def isSkewedTree(root): height, size = findHeight(root) return height == size if __name__ == '__main__': root = Node(15) root.right = Node(30) root.right.left = Node(25) root.right.left.left = Node(18) root.right.left.left.right = Node(20) if isSkewedTree(root): print('The binary tree is skewed') else: print('The binary tree is not skewed') |
Another solution is to traverse the tree in a preorder fashion and check the total number of children for each node. If both the left child and the right child exists for a node, the binary tree cannot be skewed. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Function to check if each node of a binary tree has exactly one child bool isSkewedTree(Node* root) { // Base case: empty tree if (root == nullptr) { return true; } // return false if both the left child and the right child // exists for a node if (root->left && root->right) { return false; } // recur for the left and right subtree return isSkewedTree(root->left) && isSkewedTree(root->right); } int main() { Node* root = new Node(15); root->right = new Node(30); root->right->left = new Node(25); root->right->left->left = new Node(18); root->right->left->left->right = new Node(20); bool isSkewed = isSkewedTree(root); if (isSkewed) { cout << "The binary tree is skewed"; } else { cout << "The binary tree is not skewed"; } return 0; } |
Output:
The binary tree is skewed
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// Data structure to store a binary tree node class Node { int key; Node left, right; Node(int key) { this.key = key; this.left = this.right = null; } } class Main { // Function to check if each node of a binary tree has exactly one child public static boolean isSkewedTree(Node root) { // Base case: empty tree if (root == null) { return true; } // return false if both the left child and the right child // exists for a node if (root.left != null && root.right != null ) { return false; } // recur for the left and right subtree return isSkewedTree(root.left) && isSkewedTree(root.right); } public static void main(String[] args) { Node root = new Node(15); root.right = new Node(30); root.right.left = new Node(25); root.right.left.left = new Node(18); root.right.left.left.right = new Node(20); boolean isSkewed = isSkewedTree(root); if (isSkewed) { System.out.println("The binary tree is skewed"); } else { System.out.println("The binary tree is not skewed"); } } } |
Output:
The binary tree is skewed
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.key = data self.left = left self.right = right # Function to check if each node of a binary tree has exactly one child def isSkewedTree(root): # Base case: empty tree if root is None: return True # return false if both the left child and the right child # exists for a node if root.left and root.right: return False # recur for the left and right subtree return isSkewedTree(root.left) and isSkewedTree(root.right) if __name__ == '__main__': root = Node(15) root.right = Node(30) root.right.left = Node(25) root.right.left.left = Node(18) root.right.left.left.right = Node(20) isSkewed = isSkewedTree(root) if isSkewed: print('The binary tree is skewed') else: print('The binary tree is not skewed') |
Output:
The binary tree is skewed
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.
Exercise: Modify the solution to check for left skewed binary tree or right skewed binary tree.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)