Member Avatar for harde_1

Im trying to add Total function and isMono functions to this code. Did total already

Need help with function ismono which returns whether a tree is mono (all the elements are unique aka no element appears more than one time) or not. Please

this is the original program

#ifndef T_H

#define T_H

#include <iostream>
#include <iomanip>
using namespace std;

struct tnode {
    int info ;
    int count;
    tnode * right, *left;
};

tnode * insert(int target,tnode * t);
tnode * makenode(int x);
tnode * tsearch(int x,tnode * t);
void inorder(tnode * t);
int height(tnode * t);
int count(tnode * t) ;
int total(tnode * t) ;

#endif

int main() {
int n,c;
tnode * t = NULL, *x;
    while (cin >> n) {t=insert(n,t);cout << n <<' ';}
    cout << endl;
    inorder(t);
    cout << endl;
    c = count(t);
    cout << "count: "<< c  <<endl;
    cout << endl;
    c = height(t);
    cout << "height: "<< c  <<endl;
    cout << endl;
    c=200;
    while (c-->0) if (x = tsearch(c,t)) cout << c << " is on the tree."<<endl;
return 0;
}

#include "t.h"

int count(tnode * t) {
    if (t == NULL) return 0;
    return 1 +  count(t->left) + count (t->right);
}

#include "t.h"

int height(tnode * t) {
    if (t == NULL) return -1;
    return 1 + max(height(t->left) , height (t->right));
}

#include "t.h"

//write out t in order
void inorder(tnode * t) {
    if (t == NULL) return;
    inorder (t->left);//write out lst in order
    cout <<setw(5) << t->info <<setw(5) << t->count<< endl;
    inorder (t->right);//write out rst in order
}

#include "t.h"

tnode * insert(int x, tnode * t) {
tnode * tmp = tsearch(x,t);
if (tmp != NULL) {
    tmp->count++;
    return t;
}
if (t == NULL) return makenode(x);
if ( x < t->info ) {
    t->left = insert(x,t->left);
    return t;
}
t->right = insert(x,t->right);
return t;
}

#include "t.h"

tnode * makenode(int x) {
tnode * t = new tnode;
    t->info =x;
    t->count =1;
    t->right = t->left = NULL;
return t;
}
  • 3 Contributors
  • 2 Replies
  • 322 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by deceptikon

Dani AI

Generated

Quick clarification first: "mono" here means each logical element appears only once. In the code shown by the insert path increments tnode::count for duplicates, so you will not get two nodes with the same info value — duplicates are represented by count > 1. That makes the simplest, fastest test to verify every node’s count equals 1 (as pointed out). Avoid the approach suggested by (calling tsearch for each node) because that turns a linear check into an O(n·h) or worst-case O(n^2) operation on an unbalanced tree.

A robust O(n) solution: do one inorder traversal and bail out as soon as you see any node with count > 1. This keeps extra memory to O(h) (the stack or recursion depth) and runs in linear time.

#include <stack>

bool isMono(const tnode* root) {
    if (!root) return true;
    std::stack<const tnode*> st;
    const tnode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        if (cur->count > 1) return false;
        cur = cur->right;
    }
    return true;
}

If you ever work with a BST variant that doesn't keep a count field (duplicates stored as separate nodes), use an inorder check that compares each node’s info to the previous value; duplicates appear as adjacent equal values. Example (non-counted tree):

bool isMonoNoCounts(const tnode* root) {
    if (!root) return true;
    std::stack<const tnode*> st;
    const tnode* cur = root;
    const tnode* prev = nullptr;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        if (prev && cur->info == prev->info) return false;
        prev = cur;
        cur = cur->right;
    }
    return true;
}

Practical tips: add bool isMono(const tnode*); to your header, include <stack> and prefer the O(n) traversal. If isMono returns false unexpectedly, print inorder info/count to confirm whether duplicates are tracked via count or were mistakenly inserted as separate nodes.

Recommended Answers

All 2 Replies

Member Avatar for Gonbe

Not having a compiler handy, so treat the following as kind-of pseudo code, but if performance is no requirement you could define it as

bool isMono(const tNode* t)
{
    if (t == NULL) 
        return true;
    else
        return tsearch(t->info, t->left) == NULL && tsearch(t->info, r->right) == NULL && isMono(t->left) && isMono(r->right);
}

(assuming tsearch on an empty tree results in a NULL pointer)

Member Avatar for deceptikon

The tree being "mono" is already an invariant as far as nodes go, you'll never have two nodes with the same key. However, you can check for the tree being "mono" with a simple traversal and a test to see if any of the counts are greater than 1 (which may be what you mean by "mono"):

bool isMono(tnode *root)
{
    if (!root) {
        return true;
    }

    if (root->count > 1) {
        return false;
    }

    return isMono(root->left) && isMono(root->right);
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.