CODEWITHSUNDEEP
calgorithmtree
Ajay Yadav
Ajay Yadav

Reputation: 1645

Tree satisfying BST property But I think it is not BST?

Today i am doing a problem on Binary Trees during which I found a structure of BSTree which is satisfying property : "Every node has smaller value on its left child and greater value on its right child". But it is not a BST ( in my opinion ) because root has smaller value than one of its grand child.Please Explain me all this .

Binary tree :

      7
     /  \
    4    10
   / \
  2   8

Tell me is this BST or Not ? Explain .

Upvotes: 5

Views: 336

Answers (3)

Geek
Geek

Reputation: 27183

It is not a BST , as an inorder traversal of the tree will not provide a sorted output . The main culprit is the node with value 8 . It is lying in the left subtree of the root node but is greater than the root node which is 4 .

Upvotes: 0

tojrobinson
tojrobinson

Reputation: 359

A more correct definition of a BST can be found here:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

So, although your tree satisfies the specific case of every node having a smaller value to its left and a larger value to its right, it does not satisfy the more general case involving the left and right subtrees, and is therefore not a BST.

Upvotes: 4

Drakosha
Drakosha

Reputation: 12155

It's not, 8 > 7 but 8 is on left side of 7.

Upvotes: 4

Related Questions