0

I know how to check whether a given tree is binary tree or not. But the problem is what if the tree contains duplicate values.

How to check whether a tree which may contains duplicate values is a binary search tree or not The duplicate values must be on the right side of a tree/sub tree.

vinter
  • 466
  • 1
  • 3
  • 13

1 Answers1

0

In the binary search tree program when you add a check if the tree on the right is BST or not, then check if the value on the right is greater or equal to. For instance,

bool BST(BinaryTree root){
 bool returnValue=false;
  if(root!=null){
    if(root.left!=null){
      if (root.left.data < root.data){
       returnValue=BST(root.left);
      }
    }
    if(root.right!=null){
       if(root.right.data >= root.data){
          returnValue=BST(root.right);
       }
   }
   return returnValue;
 }
}
MNKO
  • 26
  • 3
  • Your code has many mistakes..what if root.right is None and also see this case in level order 2 1 2 and also 4 3 4 2 6 – vinter Apr 02 '20 at 08:04
  • you right about the null check which I have edited, please note the code above is just for reference. To explain about the check for duplicates. You can also use range to verify if it is a BST with duplicates. – MNKO Apr 02 '20 at 08:25
  • You can also refer a similar discussion https://stackoverflow.com/questions/16727871/bst-with-duplicates – MNKO Apr 02 '20 at 08:31
  • You are checking or comparing the child nodes only with the parent nodes. What if the leaf node is greater than the root node. LEVEL ORDER EXAMPLE-- 4 2 6 1 5 5 8 – vinter Apr 02 '20 at 09:28