Binary Search Trees

Question

This is some code found on wikipedia regarding BST :

# 'node' refers to the parent-node in this case
 def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

Now here's a Binary Tree :

       10
    5        12
  3   8    9   14
     4 11  

If I am searching for 11, and I follow the algorithm up there, I start with 10, I go right to 12, and then left to 9. And I reach the end of the tree without finding 11. But 11 exists in my tree, it's just on the other side.

Can you please explain what are the restrictions in a Binary Tree for this algorithm to work on my tree ?

Thanks.

Answer 1

Do not confuse between Binary Tree and Binary Search Tree. The binary search tree (in short called as BST) is a special type of binary tree where all the nodes on the left are lesser than or equal to the parent node and all the nodes right are greater than the parent node.

Whereas the example you've given is just a Binary Tree and not a Binary Search Tree. You can see that the value 11 and 14 are left to the parent node 10 which violates the BST property. Take a look here for Binary search trees.

Answer 2

You have placed the nodes 14 and 11 in the wrong place. From the Wikipedia article on BSTs:

• 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 the node's key.
• Both the left and right subtrees must also be binary search trees.

As you can see, both 14 and 11 are greater than 8.

Answer 3

The tree you presented in not a BST. 11 and 14 would have never been inserted to the left of 10, and that's why the algorithm doesn't search there. 9 is also out of place.

Insertion according to Wikipedia:

Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.

You can tell that a Binary Tree is a BST if it has these properties (also from Wikipedia):

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

Answer 4

It's just because your tree is not a binary search tree: it is not ordered correctly. The BST is build as described in the algorithm actually. For instance in your tree: the node '9' is not at the right position because as 9 < 10 it should be under the left branch of your root node '10'. Same for '14' and '11' which should be on the right branch.

for instance a BST could sth like this:

    10
  5    11
3   8    12
          14

Answer 5

your tree is not a binary search tree