Problem Statement

    Write a method to validate if given binary tree is a binary search tree or not.

Solution

    All binary search trees are binary trees but not all binary trees are binary search trees(BSTs). A binary tree can have max of two children at each node. When left child of a node (and all nodes in left subtree) is smaller or equals to root and right child of node (and all nodes in right subtree) is grater then it is called a Binary Search Tree. More details on BST can be found here.

Method 1: Keep min and max value for each node

    We know a left child and all nodes in left subtree should be less than or equal to its parent and exactly opposite for right node and all nodes in right subtree satisfies condition for BST. We will start with keeping range of integer’s min and max values for root and update them for each level accordingly. Look at the code below:

    static bool IsBinarySearchTreeTraversal(Node root, int minValue, int maxValue)
    {
        if (root == null)
        {
            return true;
        }

        // Check BST condition on each node
        // Initial min is int.max and max is int.max
        // For left node, max should not be more than root's value and for right node, min should be grater than root's value
        if (root.Key > minValue && root.Key < maxValue)
        {
            // Adding 1 in max for root's key to satisfy duplicates when root and its left can be same value
            return IsBinarySearchTreeTraversal(root.Left, minValue, root.Key + 1) && IsBinarySearchTreeTraversal(root.Right, root.Key, maxValue);
        }

        return false;
    }

In above code we are checking min and max range for each node if satisfied then we get into next level where for left node max is updated to (root’s key + 1) and for right node min is updated to (root’s key). So when recursive call gets into next level it checks updated min and max values for nodes. Lets run the code.

    static void Main(string[] args)
    {
        Node root = new Node(20);
        root.Left = new Node(15);
        root.Right = new Node(25);
        root.Left.Left = new Node(10);
        root.Left.Right = new Node(18);
        root.Right.Right = new Node(30);

        /*
            
                20
                /\
              15  25
             /  \   \
            10  18   30
        */

        Console.WriteLine($"IsBinarySearchTree (TraversalAlgo): {IsBinarySearchTreeTraversal(root, int.MinValue, int.MaxValue)}");
    }

Output

IsBinarySearchTree (TraversalAlgo): True

Method 2: Use Inorder traversal and additional pointer to keep track of last item

We know how Inorder traversal works, firstly it goes to left most node of a tree and from there it traverse back to parent and then look for right node. So the traversal on a node should be as shown in picture below.

So when control starts at Left we use additional pointer to store it. When control goes to Root we compare Root with Left (stored in additional pointer), we also set pointer to Root. At the end we compare Right with Root (stored in additional pointer). So flow checks if Root > Left and Right > Root, if yes then returns true. Look at the code below for better understanding.

    // Need extra pointer to keep previous value
    static Node prev;
    static bool IsBinarySearchTreeInOrder(Node current)
    {
        if (current == null)
        {
            return true;
        }

        if (IsBinarySearchTreeInOrder(current.Left))
        {
            if (prev != null)
            {
                // Root's left should be smaller and right should be greater
                // Traversal of nodes in InOrder is left, then root than right
                //     root
                //     / \
                //  Left  Right
                // So when prev is left and current is root then condition should satisfy current>prev
                // When prev is root and current is right then condition should satisfy current>prev
                // Same in both cases
                if (current.Key < prev.Key)
                {
                    return false;
                }
            }

            prev = current;

            return IsBinarySearchTreeInOrder(current.Right);
        }

        return false;
    }

Let’s run this code.

    static void Main(string[] args)
    {
        prev = null;
        var root = new Node(20);
        root.Left = new Node(20);
        root.Right = new Node(25);

        /*
            
                20
                /\
              20  25
        */

        Console.WriteLine($"IsBinarySearchTree (In Order TraversalAlgo): {IsBinarySearchTreeInOrder(root)}");
    }

Output

IsBinarySearchTree (In Order TraversalAlgo): True

Now let's modify Right node's value to 20 and observe:

    static void Main(string[] args)
    {
        prev = null;
        var root = new Node(20);
        root.Left = new Node(20);
        root.Right = new Node(20);

        /*
            
                20
                /\
              20  20
        */

        Console.WriteLine($"IsBinarySearchTree (In Order TraversalAlgo, duplicate node in right): {IsBinarySearchTreeInOrder(root)}");
    }

Output

IsBinarySearchTree (In Order TraversalAlgo, duplicate node in right): True

It still says true but that should not be the case. So this method works only when there are no duplicates.