-2
      10
     /  \
    /    \
   9      13
  / \ 
 /   \
5    12

If No, why ? If yes, why inorder traversal (5,9,12,10,13) on this don't results in a sorted sequence of nodes ?

Note: The leaf 5 is left child of 9 and leaf 12 is right child of 9.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
Shailesh Pratapwar
  • 4,054
  • 3
  • 35
  • 46

1 Answers1

0

No, it's not a valid search tree. While it's balanced (difference between highest and lowest leaf is one or less), the ordering of the 10 and 12 is incorrect.

It would be valid if it were:

     12
    /  \
   /    \
  9      13
 / \
5   10

The basic rule is that everything in the entire left sub-tree of a node should be lesser than that node's value. And, accordingly, everything in the right sub-tree should be greater.

Clearly 12 is not less than 10 so your given tree is not much good as a binary search tree. If you went looking for 12, the first thing you would do from the root node is to descend into the right sub-tree, where you wouldn't be able to find it.

You can validate a binary search tree with the following recursive pseudo-code:

def isValid (node):
    # Gone below leaf, so is valid.

    if node == NULL:
        return true

    # Check immediate children if they're there.

    if node.left <> NULL:
        if node.value < node.left.value:
            return false

    if node.right <> NULL:
        if node.value > node.right.value:
            return false

    # Check individual sub-trees (both must be valid).

    if not isValid (node.left):
        return false

    return isValid (node.right)

and call it with the root node:

wholeTreeValid = isValid (root)
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • I assumed that we only consider the only left and right child for comparison. However, the fact is we should consider all nodes in child subtree for comparisons. – Shailesh Pratapwar Jun 18 '14 at 02:40