# Thread: determine if tree is strictly binary bst

1. ## determine if tree is strictly binary bst

Hi, need a little help on this one.
I need to write a member function to determine if my BST is
strictly binary or not. The function should do this through a
series of if statements, and simply printing out a message.
The complication is, it needs recursive calls, and I'm not too good
with those.
I've written the function, and it works, but it's printing a tree ahead of
time, so there are several printouts when there supposed to be only one.

Here is the function:

void BST::strict() //this function is public to be called by main()
{
strict(theroot);
}
//

//private functon, gets a pointer to tree node.
//called by public strict().
//Will determine if a tree is strictly binary
//or not, and then rint a message.
void BST::strict(Tnode *p)
{

bool ans;
ans =false;

if(p == NULL)

ans = true;
else if((p->right == NULL && p->left == NULL) || (p->right != NULL && p->left != NULL)){
strict(p->left);
strict(p->right);

ans =true;
}
else if((p->right == NULL && p->left != NULL) || (p->right != NULL && p- >left == NULL)){
ans =false;
}

//else
// //cout<<"The tree is NOT strictly binary!!!"<<endl;
// ans =2;

if(ans ==true){
cout<<"The tree is strictly binary!!!"<<endl;
}
else if(ans ==false){
cout<<"The tree is NOT strictly binary!!!"<<endl;
}

}

here is the output:

Here is the 1st Tree traversal:
INORDER:
-3 1 10 54 97

PREORDER:
10 -3 1 97 54

POSTORDER:
1 -3 54 97 10

Smalest item in the tree: -3
Largest item in the tree: 97
Largest item in left subtree: 1
Smallest item in right subtree: 54

The tree is NOT strictly binary!!!
The tree is NOT strictly binary!!!
The tree is strictly binary!!!

Here is the 2nd Tree traversal:
INORDER:
7 10 20

PREORDER:
10 7 20

POSTORDER:
7 20 10

Smalest item in the tree: 7
Largest item in the tree: 20
Largest item in left subtree: 7
Smallest item in right subtree: 20

The tree is strictly binary!!!
The tree is strictly binary!!!
The tree is strictly binary!!!
The tree is strictly binary!!!
The tree is strictly binary!!!
The tree is strictly binary!!!
The tree is strictly binary!!!

Here is the 3rd Tree traversal:
INORDER:
0 1 15 19 20 20 30 81

PREORDER:
0 20 15 1 19 30 20 81

POSTORDER:
1 19 15 20 81 30 20 0

Smalest item in the tree: 0
Largest item in the tree: 81
Largest item in left subtree: 0
Smallest item in right subtree: 1

The tree is NOT strictly binary!!!

Here is the 4th Tree traversal:
INORDER:
1 3 4 5 6 8 10 11 13 15

PREORDER:
10 5 4 1 3 6 8 15 11 13

POSTORDER:
3 1 4 8 6 5 13 11 15 10

Smalest item in the tree: 1
Largest item in the tree: 15
Largest item in left subtree: 8
Smallest item in right subtree: 11

The tree is NOT strictly binary!!!
The tree is NOT strictly binary!!!
The tree is strictly binary!!!
The tree is NOT strictly binary!!!
The tree is strictly binary!!!

Here is the 5th Tree traversal:
INORDER:

PREORDER:

POSTORDER:

Smalest item in the tree:
Largest item in the tree:
Largest item in left subtree:
Smallest item in right subtree:

The tree is strictly binary!!!

Press any key to continue . . .

2. Huh? Is this true:
a BST is strict if it's empty.
a BST is strict if both left and right are strict.

Assuming this is the definition, then writing a recursive function to solve the problem shouldn't be hard. However, whilst you have indeed written a recursive function, you are not using the return value from the left/right checks. The second else-if only needs to be an else, since the if-statement is always true if the other if's failed.

--
Mats

3. This is a standalone function.... can easily be converted to member function
Code:
```bool IsStrictlyBinary(Node* root) {

if(root->left == NULL && root->right == NULL)
return true;
else if ((root->left == NULL && root->right != NULL)  ||
(root->right == NULL && root->left != NULL)	)
return false;
else
return ((IsStrictlyBinary(root->left))?IsStrictlyBinary(root->right):false);
}```

4. Originally Posted by learningToCode
This is a standalone function.... can easily be converted to member function
Thanks for your contribution, but this thread became dormant the day it began, in the first half of last year. If ashir30000 had responded with say, a problematic solution that was never corrected then perhaps you would be justified in resurrecting this thread, but as it stands I will just close it.

By the way, this:
Code:
`return ((IsStrictlyBinary(root->left))?IsStrictlyBinary(root->right):false);`
can be simplified to:
Code:
`return IsStrictlyBinary(root->left) && IsStrictlyBinary(root->right);`