Coding Interview Club

Prepare for coding interviews in simple and structured steps

Check if a Binary Tree is a Binary Search Tree (BST) using Inorder Traversal

Category: 
Problem: 

Check if a Binary Tree is a Binary Search Tree (BST) using Inorder Traversal.

Approach: 

You can traverse the tree in in-order way, and see if the elements are assending.

  • You may either put the elements into an array and see if the array is sorted in assending way,
  • or while traversing see if the current element is always greater than or equal to previous element.
    • return false is current data is less than previously printed data.
    • may use a static variable to hold the last printed value.

 

Solution: 

Class BSTChecker {

  static int LAST = Integer.MIN_VALUE;

  boolean isBSTCheck(TreeNode n)

  {

    if (n == null) return true;

    if( ! isBSTCheck(n.left) ) return false;

    if( n.data < LAST ) return false;

    LAST = n.data;

    if( ! isBSTCheck(n.right) ) return false;

    return true;

  }

}

 

Complexity

Time complexity is O(N)

Space complexity is O(log N)

Back to Top