Why is this Binary tree considered as an invalid Binary Search Tree:

CodePudding user response：

The value 22 is misplaced. The nodes at the left of the root (17) should never be greater than it. This is not only the rule for the immediate child (6), but must be true for all of the left subtree.

Just imagine you would search this tree for value 22 using a binary search: then you would compare 22 with the root's value and decide to look in the right subtree (because it is greater). You would not find it there, and so you would conclude that the tree does not have the value 22.

CodePudding user response：

Binary Tree: In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Binary Search Tree: In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

Notice that, definition involves the term subtree, not child. I think there is a little confusion in your mind about that.

• Correct definiton: store a key greater than all the keys in the node’s left subtree and less than those in its right subtree
  
• Incorrect definition: store a key greater than all the keys in the node’s left child and less than those in its right child.
  

Why subtree? Well because we want to perform the insert operation in a definite way: If we put 17, 6 and 19 to our binary tree and looking for a node place to insert 22, where should we put it?
If the second definition was true, then where to place 22 would be indefinite. We could have placed it as right child of 9 or right child of 19.
First definition requires us to put it as right child of 19.

References:
Binary Tree
Binary Search Tree