Count distinct element in a BST
#include <bits/stdc++.h>
using
namespace
std;
struct
Node {
int
data;
Node *left, *right;
Node(
int
val)
{
data = val;
left = right = NULL;
}
};
int
countDistinct(Node* root)
{
int
count = 0;
int
prev = INT_MIN;
if
(root == NULL)
return
0;
while
(root != NULL) {
if
(root->left == NULL) {
if
(root->data != prev) {
count++;
prev = root->data;
}
root = root->right;
}
else
{
Node* curr = root->left;
while
(curr->right != NULL
&& curr->right != root) {
curr = curr->right;
}
if
(curr->right == NULL) {
curr->right = root;
root = root->left;
}
else
{
if
(root->data != prev) {
count++;
prev = root->data;
}
curr->right = NULL;
root = root->right;
}
}
}
return
count;
}
int
main()
{
Node* root =
new
Node(5);
root->left =
new
Node(3);
root->left->left =
new
Node(2);
root->left->right =
new
Node(4);
root->right =
new
Node(7);
root->right->left =
new
Node(6);
root->right->right =
new
Node(8);
int
distinct = countDistinct(root);
cout <<
"Distinct elements in BST: "
<< distinct
<< endl;
return
0;
}
#include <bits/stdc++.h>
using
namespace
std;
struct
Node {
int
data;
Node *left, *right;
Node(
int
val)
{
data = val;
left = right = NULL;
}
};
int
countDistinct(Node* root)
{
int
count = 0;
int
prev = INT_MIN;
if
(root == NULL)
return
0;
while
(root != NULL) {
if
(root->left == NULL) {
if
(root->data != prev) {
count++;
prev = root->data;
}
root = root->right;
}
else
{
Node* curr = root->left;
while
(curr->right != NULL
&& curr->right != root) {
curr = curr->right;
}
if
(curr->right == NULL) {
curr->right = root;
root = root->left;
}
else
{
if
(root->data != prev) {
count++;
prev = root->data;
}
curr->right = NULL;
root = root->right;
}
}
}
return
count;
}
int
main()
{
Node* root =
new
Node(5);
root->left =
new
Node(3);
root->left->left =
new
Node(2);
root->left->right =
new
Node(4);
root->right =
new
Node(7);
root->right->left =
new
Node(6);
root->right->right =
new
Node(8);
int
distinct = countDistinct(root);
cout <<
"Distinct elements in BST: "
<< distinct
<< endl;
return
0;
}