I think the definition of Binary Search Tree is wrong (in “data-structures-algorithms-in-python”). It’s not enough to ask that the left / right children of every node are less / more than the current node, the same condition must be asked of all the nodes of the whole left and right subtrees. Otherwise the tree 3 // 1 7 // 2 4 6 8 would be considered a BST, but the 4 is a problem. It would not be found by the search algorithm.
A binary search tree is a tree data structure in which nodes are arranged according to the BST property which is as follows:
The value of the left child of any node in a binary search tree will be less than whatever value we have in that node, and the value of the right child of a node will be greater than the value in that node.
Your BST looks like:
So how can you say 4 is problem here?
Consider this example:
0th level (root): 3
1st level: 2,7
2nd level: 1, 4, 6, 8
In this example, 1 and 4 are the child nodes of 2, while 6 and 8 are the child nodes of 7.
According to your definition, this is a BST. I claim that it is not, because 4 is on the left subtree of the root but it has a higher value. This is a problem because it means that if you look for the value 4 in the tree according to your search algorithm, you will not find it, because you’ll start looking in the right subtree of the root.