Approach
The Binary Search Tree (BST) node will store an int type data structure and two node pointers for left and right nodes.
The code will have two parts - the first is for finding whether the number is a special number or not and the second is for traversing through the tree.
Pseudocode for finding Special Numbers
Algorithm_check(number)
If number is greater than 10 and number is less than 99 :
return 0
else :
Sum of digits = (number % 10) + (number /10)
Product of digits = (number % 10) x (number /10)
Final Sum = Sum of digits + Product of digits
If Final sum is equal to number :
return 1
else :
return 0
🌿 First check if the number is two-digit; it should lie within the range greater than 10 and less than 99.
🌿 If it is a two-digit number, then calculate the product of the digits, the sum of the digits and the sum of the product of digits and the sum of digits.
🌿 Check if the sum of the product of digits and the sum of digits is equal to the number itself. If it is equal then, return 1 otherwise return 0.
Pseudocode for Searching the number in the tree
Algorithm_search_and_count(node, count)
If node is NULL
return
else
flag = algorithm_check(node)
If flag is equal to 1:
Increment count
Algorithm_search_and_count(node->left, count)
Algorithm_search_and_count(node->right, count)
🌿 If the node is NULL return.
🌿 Check if the number is a special two-digit number, if it is true then increment the count.
🌿 Repeat the process for the left and right subtree.
Implementation in C++
// C++ program to count number of nodes in
// BST containing two digit special number
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node
{
struct Node *left;
int info;
struct Node *right;
};
// Function to create a new node
void insert(struct Node **root, int key)
{
if(*root == NULL)
{
(*root) = new Node();
(*root) -> left = NULL;
(*root) -> right = NULL;
(*root) -> info = key;
}
else if(key < ((*root) -> info))
insert(&((*root) -> left), key);
else
insert(&(*rt) -> right, key);
}
// Function to find if number
// is special or not
int check(int num)
{
int sum = 0, i = num, sum_of_digits, prod_of_digits ;
// Check if number is two digit or not
if(num < 10 || num > 99)
return 0;
else
{
sum_of_digits = (i % 10) + (i / 10);
prod_of_digits = (i % 10) * (i / 10);
sum = sum_of_digits + prod_of_digits;
}
if(sum == num)
return 1;
else
return 0;
}
// Function to count number of special two digit number
void countSpecialDigit(struct Node *root, int *count)
{
int x;
if(root == NULL)
return;
else
{
x = check(rt -> info);
if(x == 1)
*count = *count + 1;
countSpecialDigit(rt -> left, count);
countSpecialDigit(rt -> right, count);
}
}
// Driver program to test
int main()
{
struct Node *root = NULL;
// Initialize result
int count = 0;
// Function call to insert() to insert nodes
insert(&root, 50);
insert(&root, 29);
insert(&root, 59);
insert(&root, 19);
insert(&root, 53);
insert(&root, 556);
insert(&root, 56);
insert(&root, 94);
insert(&root, 13);
// Function call, to check each node for
// special two digit number
countSpecialDigit(root, &count);
cout<< count;
return 0;
}
You can also try this code with Online C++ Compiler
Implementation in Java
// Java program to count number of nodes in BST containing two digit special number
// A binary tree node
class Node
{
int info;
Node left, right;
Node(int d)
{
info = d;
left = right = null;
}
}
class BinaryTree{
static Node head;
static int count;
// Function to create a new node
Node insert(Node node, int info)
{
// If the tree is empty, return a new,
// single node
if (node == null)
{
return (new Node(info));
}
else
{
// Otherwise, recur down the tree
if (info <= node.info)
{
node.left = insert(node.left, info);
}
else
{
node.right = insert(node.right, info);
}
// return the (unchanged) node pointer
return node;
}
}
// Function to find if number
// is special or not
static int check(int num)
{
int sum = 0, i = num,
sum_of_digits,
prod_of_digits;
// Check if number is two digit or not
if (num < 10 || num > 99)
return 0;
else
{
sum_of_digits = (i % 10) + (i / 10);
prod_of_digits = (i % 10) * (i / 10);
sum = sum_of_digits + prod_of_digits;
}
if (sum == num)
return 1;
else
return 0;
}
// Function to count number of special
// two digit number
static void countSpecialDigit(Node rt)
{
int x;
if (rt == null)
return;
else
{
x = check(rt.info);
if (x == 1)
count = count + 1;
countSpecialDigit(rt.left);
countSpecialDigit(rt.right);
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
Node root = null;
root = tree.insert(root, 50);
tree.insert(root, 29);
tree.insert(root, 59);
tree.insert(root, 19);
tree.insert(root, 53);
tree.insert(root, 556);
tree.insert(root, 56);
tree.insert(root, 94);
tree.insert(root, 13);
// Function call
countSpecialDigit(root);
System.out.println(count);
}
}
You can also try this code with Online Java Compiler
Also check out Addition of Two Numbers in Java here.
Implementation in Python
# Python3 program to count number of nodes in
# BST containing two digit special number
# A Tree node
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# Function to create a new node
def insert(node, data):
global succ
# If the tree is empty, return
# a new node
root = node
if (node == None):
return Node(data)
# If key is smaller than root's key,
# go to left subtree and set successor
# as current node
if (data < node.data):
root.left = insert(node.left, data)
# Go to right subtree
elif (data > node.data):
root.right = insert(node.right, data)
return root
# Function to find if number
# is special or not
def check(num):
sum = 0
i = num
#sum_of_digits, prod_of_digits
# Check if number is two digit or not
if (num < 10 or num > 99):
return 0
else:
sum_of_digits = (i % 10) + (i // 10)
prod_of_digits = (i % 10) * (i // 10)
sum = sum_of_digits + prod_of_digits
if (sum == num):
return 1
else:
return 0
# Function to count number of special
# two digit number
def countSpecialDigit(root):
global count
if (x == 1):
if (root == None):
return
else:
x = check(root.data)
c += 1
countSpecialDigit(root.left)
countSpecialDigit(root.right)
# Driver code
if __name__ == '__main__':
root = None
# Initialize result
count = 0
# Function call to insert() to
# insert nodes
root = insert(root, 50)
root = insert(root, 29)
root = insert(root, 59)
root = insert(root, 19)
root = insert(root, 53)
root = insert(root, 556)
root = insert(root, 56)
root = insert(root, 94)
root = insert(root, 13)
# Function call, to check each node
# for special two-digit number
countSpecialDigit(root)
print(count)
You can also try this code with Online Python Compiler
Output
The Binary Search Tree nodes have the following values
50, 29, 59, 19, 53, 556, 13, 56, 94.
There are three Special characters in BST - 29, 19 and 59.
So, the count is 3.
Time Complexity
We are visiting all the nodes only once. So, the time complexity of the program is O(n), where n is the number of nodes of the tree.
Space complexity
The space is required for the n nodes in the tree so, the space complexity of the code is O(n) for n nodes of the tree.
Check out this problem - Mirror A Binary Tree
You can also read about - Strong number in c
Frequently Asked Questions
What are the two rules of a Binary Search Tree?
The first rule is that there should be at least one root node present in the tree. The second rule is that the left subtree contains values less than the root node value and the right subtree contains a value greater than the root node value.
What is the height of a binary search tree?
In a binary search tree, the height is defined as the longest path from the root node to the leaf node of the tree.
Can Binary Search Tree have duplicate values?
By definition of a Binary search tree, the left subtree nodes will have values smaller than the root node and the right subtree nodes will have values greater than the root node, so a BST CANNOT have duplicate values.
Conclusion
Pat yourself on the back for finishing this article. In this article, we discussed the problem of counting the number of nodes with a special two-digit number in a Binary Search Tree. We discussed the implementation code in three languages, C++, Java and Python. We concluded that the time complexity of the code and the space complexity are both O(n), where n is the number of nodes in the Binary Search Tree (BST).
If you are interested in knowing more about Binary Search Trees and Tree data structure, we recommend you read some of our articles -
🔥 Introduction to Binary Search Tree
🔥 Sum and the Product of minimum and maximum elements of a Binary Search Tree
🔥 Count the Nodes in BST that lie in a given Range
Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and Algorithms, Competitive Programming, System Design, and many more courses.
If you want to Practice top Coding Problems, attempt mock tests, or read interview experiences, head to the Coding Ninjas Studio, our practice platform.
We wish you Good Luck!🎈 Please upvote our blog and help other ninjas grow.
84+ registered