Strict Binary Tree

[Gaiety]

Hello,

i have written the code for checking a given tree is strict binary or not.

i tried the following code but i am not getting the correct result.
and i unable to understand how to check.

int strict ( BST_t *p ){

if( p == NULL )
        return 1;

else if( ( p->right == NULL && p->left == NULL ) || ( p->right != NULL && p->left != NULL ) )
{
        return strict( p->left );
        return strict( p->right );
}
else
        return 0;
}

in this case the program is returning from
strict(p->left) only its not entering strict (p->right).

how to make the function enter both the links.

the other thing is if the tree is empty ( no nodes at all) then is it a strict binary tree.

please do the need i have been trying for this for few days but unable to get the idea..

[Tom Gunn]

When you say 'strict binary tree', you mean that each node has only two links? You can do it, but if your node struct only has left and right pointers, it is kind of pointless to do a test that is guaranteed at design time. ;)

If you mean to test for a strict binary search tree, you need to do a key value relation test:

int IsStrictBst(struct node* root)
{
    if (root)
    {
        if ((root->left && root->left->dat >= root->dat) ||
            (root->right && root->right->dat <= root->dat))
        {
            return 0;
        }
    }
    else return 1;
}

[Gaiety]

When you say 'strict binary tree', you mean that each node has only two links? You can do it, but if your node struct only has left and right pointers, it is kind of pointless to do a test that is guaranteed at design time. ;)

If you mean to test for a strict binary search tree, you need to do a key value relation test:

int IsStrictBst(struct node* root)
{
    if (root)
    {
        if ((root->left && root->left->dat >= root->dat) ||
            (root->right && root->right->dat <= root->dat))
        {
            return 0;
        }
    }
    else return 1;
}

Thank you TOM for your reply.

but i dont understand how can we ensure a binary tree is strict just by checking only root and its children .

i have few questions:
for the tree to be strict does it must be a BST?

if its a BST any way in BST all the left subtrees are less than the root and all the right sub trees are greater than the root.
but you checked it reverse.

[Tom Gunn]

but i dont understand how can we ensure a binary tree is strict just by checking only root and its children .

That was my mistake. I posted an incomplete example. That function is supposed to be recursive. I will try again:

int IsStrictRoot(struct node* root)
{
    return !((root->left && root->left->dat >= root->dat) ||
             (root->right && root->right->dat <= root->dat));
}

int IsStrictBst(struct node* root)
{
    if (root)
    {
        return IsStrictBst(root->left) && 
               IsStrictBst(root->right) && 
               IsStrictRoot(root);
    }
    else return 1;
}

The rule for a strict binary search tree is that the left node has a smaller value than the root and the right node has a larger value than the root. That is assuming no duplicate values are allowed in the tree. The comparison can be changed to support that duplicates easily. :)

for the tree to be strict does it must be a BST?

For a tree to be strict you need to define what strict is. A BST has a node order requirement, but if you have a binary tree that is not a BST, there has to be some ordering that makes it strict, or the design of the tree allows more than one child node and you want to allow only up to two at run time.

but you checked it reverse.

It is a reverse test for failure. Here is the truth table for that comparison:

I = Invalid
V = Valid
* = NULL

   | * | V | I |
---+---+---+---+
 * | 1 | 1 | 0 |
---+---+---+---+
 V | 1 | 1 | 0 |
---+---+---+---+
 I | 0 | 0 | 0 |
---+---+---+---+

[Gaiety]

That was my mistake. I posted an incomplete example. That function is supposed to be recursive. I will try again:

int IsStrictRoot(struct node* root)
{
    return !((root->left && root->left->dat >= root->dat) ||
             (root->right && root->right->dat <= root->dat));
}

int IsStrictBst(struct node* root)
{
    if (root)
    {
        return IsStrictBst(root->left) && 
               IsStrictBst(root->right) && 
               IsStrictRoot(root);
    }
    else return 1;
}

The rule for a strict binary search tree is that the left node has a smaller value than the root and the right node has a larger value than the root. That is assuming no duplicate values are allowed in the tree. The comparison can be changed to support that duplicates easily. :)

For a tree to be strict you need to define what strict is. A BST has a node order requirement, but if you have a binary tree that is not a BST, there has to be some ordering that makes it strict, or the design of the tree allows more than one child node and you want to allow only up to two at run time.

It is a reverse test for failure. Here is the truth table for that comparison:

I = Invalid
V = Valid
* = NULL

   | * | V | I |
---+---+---+---+
 * | 1 | 1 | 0 |
---+---+---+---+
 V | 1 | 1 | 0 |
---+---+---+---+
 I | 0 | 0 | 0 |
---+---+---+---+

i have wriitten the following code and checked for five levels its working fine. but i am not comparing the values of the nodes.

is it the correct way ?

int strict(struct node * root)
{
if ( root )
{
if( root -> left && root->right )
return strict(root -> left ) && strict (root ->right );
else if( !root -> left && !root->right )
return 1;
else
return 0;
}
else
return 0;
}

[Tom Gunn]

i have wriitten the following code and checked for five levels its working fine. but i am not comparing the values of the nodes.

is it the correct way ?

That should work. So your definition of a strict tree is where each node has either 0 or 2 children?