Check if a Binary Tree is a Binary Search Tree (BST) using Property of Binary Tree

Approach

  • For a BST, all left nodes should be less than or equal to current node and current node must be less than all right nodes.

  • We will have a recursive function that checks if this property is true for every node and all its sub trees:

    • If the method get null node, it may return true, and should be first checked (exit condition for the recursion).

    • Check if 'left nodes is less than or equal to current node and current node must be less than all right nodes.

    • Then call the method for subtrees and see if the follow the property of BST

 

Solution

checkIfBST(TNode n, int min, int max)

{

  if(n==null)

    return true;

 

  if(n.data <=min || n.data > right)

    return false;

  

  boolean leftIsBST = checkIfBST(n.left, min, n.data);

  if(!leftIsBST)

    return false;

 

  boolean rightIsBST = checkIfBST(n.right, n.data, max);

  if(!rightIsBST)

    return false;

 

    return true;

}

 

The recursive function will be initially passed with the root node, Integer.MIN_VALUE and Integer.MAX_VALUE.

  • E.g. checkIfBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

 

Complexity

Time complexity is O(N)

Space complexity is O(log N)

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) Arrays (1) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (55) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (5) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (9) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (7) Javascript Frameworks (1) Java SE Professional (1) JPA 1 - Module (6) JPA 1 - Modules (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)