Trees: Is This a Binary Search Tree?

  • + 3 comments

    Maybe we should explain a little further. The Wikipedia algorithm consists of simply doing a recursive binary tree search and then attaching a node when you hit null.

    If somebody assumes the input is processed in order, they would be confused because the sample tree given on the problem page would be impossible to build, as would your example tree.

    Your data is 1 2 3 4 5 6 7

    The initial node is null, so the first node attached will have value 1, and 1 will be the root of your tree.

    Based on your example, it looks like there's an assumption that the input is expected to be an ordered array, and thus that the root of any given (sub-)tree can be determined by simply taking the middle value. Something like this:

    	/* A function that constructs Balanced Binary Search Tree 
    	from a sorted array */
    	Node sortedArrayToBST(int arr[], int start, int end) {
    
    		/* Base Case */
    		if (start > end) {
    			return null;
    		}
    
    		/* Get the middle element and make it root */
    		int mid = (start + end) / 2;
    		Node node = new Node(arr[mid]);
    
    		/* Recursively construct the left subtree and make it
    		left child of root */
    		node.left = sortedArrayToBST(arr, start, mid - 1);
    
    		/* Recursively construct the right subtree and make it
    		right child of root */
    		node.right = sortedArrayToBST(arr, mid + 1, end);
    		
    		return node;
    	}
    

    The problem should state that the input is in the order that the in-order traversal of the tree would yield, if that is the case.

    Actual test case:
    2
    1 2 4 3 5 6 7

    Output:
    No

    Let's test the in-order assumption:
    1: We take the middle of {1 2 4 3 5 6 7}, which is 3, and it's the first node inserted, so it becomes the root
    2: We take the middle of {1 2 4}, which is 2
    3: 2 is less than 3, so we attach it to the left
    4: We take the middle of {5 6 7}, which is 6

          3
         / \
        2   6
      
    

    5: We take the middle of {1}, which is 1, and goes left of 2, and the middle of {4}, which is 4, and goes right of 2; we do the same for the right side of the array, and get:

            3
          /   \
         2     6
        / \   / \
       1   4  5  7
    

    And we see the problem - the (4) node is in the left sub-tree of the (3) node, which violates the binary search tree definition. Thus we return false, the stub code prints "No," and we have confirmed the assumption of the input order.