Tuesday, March 24, 2015

if binary tree is binary search tree

It is bit tricky to get it working for duplicates, int.min and int.max values. Top-down approach.
is-bst-main(node):
    if node == null:
        return false
    return is-bst(node)
// works for duplicates but does not work for int.min values
is-bst(node, min = int.min, max = int.max):
    if node == null:
        return true
    if node.value <= min || max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)
// works for duplicates and int.min values (and int.max values too)
is-bst(node, min = null, max = null):
    if node == null:
        return true
    if min != null && node.value <= min
        return false
    if max != null && max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max))

Examples:
//1
      20
   10
10    10 --incorrect node

//2
      20
   10
10    11
    10 --incorrect

//3
      int.min --correct node

Another logic that works for duplicates. The null checks are required for int.max and int.min values.
max(left subtree) <= node.value < min(right subtree)
// inefficient
is-bst(node):
    if node == null:
        return true
    if node.left != null && !(max(node.left) <= node.value):
        return false
    if node.right != null && !(node.value < min(node.right)):
        return false
    return is-bst(node.left) && is-bst(node.right)

max(node):
    if node == null:
        return int.min
    return math.max(node.value, max(node.left), max(node.right))

min(node):
    if node == null:
        return int.max
    return math.min(node.value, min(node.left), min(node.right))

Another way is to "bubble up" during dfs. For a node, return min and max if node's subtree is bst else null. If node's left or right subtree returns null then bubble it up. Bottom-up approach.
// efficient
is-bst-main(node):
    if node == null:
        return false
    return get-min-max(node) != null

{min, max} get-min-max(node):
    if node == null:
        throw
    min = max = node.value
    if node.left != null:
        left = get-min-max(node.left)
        if left == null || !(left.max <= node.value):
            return null
        min = left.min
    if node.right != null:
        right = get-min-max(node.right)
        if right == null || !(node.value < right.min):
            return null
        max = right.max
    return {min, max}

[Hat tip to ctci]

No comments:

Post a Comment