Binary Search Tree

Question

Consider the following routine

bool do(struct node *root)
{  
    if(!root)
       return true;
    else if(( root ---> left != NULL && root ---> data < root ---> left---> data)
||(root-->right != NULL && root ---> data > root ----> right ----> data))
       return false;
    else
      return (do( root---> left )&& do(root---> right));
}

What does they do() check whether a given tree is:

$A)$ Max heap       $B)$ Min Heap      $C)$BST      $D)$ Binary Tree 

Comments

C ??

---

yes, can you explain?

---

 else if(( root ---> left != NULL && root ---> data < root ---> left---> data)
||(root-->right != NULL && root ---> data > root ----> right ----> data))
       return false;

This condition is checking whether the left node is less than root and right node is greater than root => which is a constraint for BST.

 

Answer 1

Answer: C

BST exhibit below properties:

1. Every element in the left should be less than or equal to the root.

2. Every element on the right side is greater than or equal to the root.

3. It has to be a binary tree.

 

  else if(( root ---> left != NULL && root ---> data < root ---> left---> data)
||(root-->right != NULL && root ---> data > root ----> right ----> data))

This condition checks if the root's left is null or not. If it's not Null then check if the data of left is less than the root or not.

If its less than the root then recursively check the further nodes.

Similarly, the right node is being checked.