Special Two-Digit Numbers in a Binary Search Tree in Java
A binary tree is a type of tree data structure where each parent node can have a maximum of two child nodes. To put it another way, for every parent node, there can be zero, one, or two child nodes. There can be no more than two child nodes for the parent node.
A binary tree data structure known as a Binary Search Tree is one in which
- The node's left subtree only contains nodes whose values are lower than the node's value.
- Only nodes with values greater than the node's values are present in the right subtree of the node.
- Every BST is required for both the left and right subtrees.
Special Number: When a number's product of its digits and the sum of its digits are equal to the number itself (taken as input), it is referred to as a special two-digit number. The below are the examples for the Special number.
If number = 39
The digits of a number are 3 and 9.
Now, the Sum of the Digits (SOD) is 3 + 9 = 12
The Product of the Digits (POD) is 3 * 9 = 27
The sum of the SOD and POD = 12 +27 = 39.
Therefore, 39 is a Special Number.
Example 1:
Input:
Output:
The total number of special two-digit numbers in a Binary Search tree is 3
Explanation:
In the given data 35, 10, 59, 79, 42, 19, and 5, after arranging in the Binary tree according to the rules, the special number is identified such that the sum of the SOD and POD should be equal to the taken number. Hence, it returns the count of the special numbers present in the tree. Thus, the output is printed as 3.
Approach: Using Recursion
Check for a unique two-digit number in each node's data by iteratively traversing each tree node with a variable count. The variable count will be increased if it exists. Return count at the end. In addition to two node pointers for the left and right nodes, the Binary Search Tree (BST) node will have an int-type data structure.
In order to determine whether a given number is special or not, the initial element of the program will perform this, and the subsequent section will traverse the tree.
Algorithm:
Step 1: To begin with, determine if the number is two digits; if so, it should be between 10 and 99.
Step 2: If the number has two digits, then calculate the product of the digits, the sum of the digits, and the product of the sum of the digits combined.
Step 3: Determine whether the number itself equals the sum of the digits plus the product of the digits. Return 1 if the values are equal; return 0 if not.
Step 4: Return if the node is NULL.
Step 5: Determine whether the number is a unique two-digit number; if so, increase the count.
Step 6: Carry out the same steps for the subtrees on the left and right until the whole binary tree is traversed.
Implementation:
FileName: SpecialDigitBinaryTree.java
import java.io.*;
import java.util.*;
class Node
{
int data;
Node leftnode, rightnode;
Node(int d)
{
data = d;
leftnode = rightnode = null;
}
}
public class SpecialDigitBinaryTree
{
static Node head;
static int count;
// The function for adding a new node
Node insert(Node newnode, int data)
{
// Return a new, empty tree if the tree
// a single node
if (newnode == null)
{
return (new Node(data));
}
else
{
// If not, continue below the tree.
if (data <= newnode.data)
{
newnode.leftnode = insert(newnode.leftnode, data);
}
else
{
newnode.rightnode = insert(newnode.rightnode, data);
}
// give back the node pointer (unchanged)
return newnode;
}
}
// Method for determining whether or not the number is a special digit
static int check(int n)
{
int sum = 0, i = n,
SOD,
POD;
// Verify if the number has two digits or not.
if (n < 10 || n > 99)
return 0;
else
{
SOD = (i % 10) + (i / 10);
POD = (i % 10) * (i / 10);
sum = SOD + POD;
}
if (sum == n)
return 1;
else
return 0;
}
// A function to count the number of unique two-digit numbers
static void SpecialDigit(Node sd)
{
int x;
if (sd == null)
return;
else
{
x = check(sd.data);
if (x == 1)
count = count + 1;
SpecialDigit(sd.leftnode);
SpecialDigit(sd.rightnode);
}
}
public static void main(String[] args)
{
SpecialDigitBinaryTree treenode = new SpecialDigitBinaryTree();
Node rootnode = null;
rootnode = treenode.insert(rootnode, 35);
treenode.insert(rootnode, 10);
treenode.insert(rootnode, 59);
treenode.insert(rootnode, 79);
treenode.insert(rootnode, 42);
treenode.insert(rootnode, 19);
treenode.insert(rootnode, 5);
SpecialDigit(rootnode);
System.out.println("The total number of special two-digit numbers in a Binary Search tree is " + count);
}
}
Output:
The total number of special two-digit numbers in a Binary Search tree is 3
Complexity Analysis:
The time complexity is O(N), where N is the number of nodes in the tree.
The height of the tree, h, determines the space complexity, which is O(h), with the recursive call stack using the additional space.