Validate Binary Search Tree (Check for Binary Search Tree)

Problem Statement: You have been given root of a binary tree. Your task is to find whether the given binary tree is valid binary search tree or not.

A binary tree is considered valid if it satisifes below conditions:

• 1. Left subtree of a node contains only nodes with values less than the node's value.
• 2. Right subtree of a node contains only nodes with values greater than the node's value.
• 3. Both the left and right subtrees must be binary search trees.

Example:

Input: root = [10, 8, 25, 5, 9, 22]
Output: true

Approach 1:

Simple inorder traversal and storing the nodes value in ArrayList and lastly checking whether the ArrayList is in sorted order or not. If the ArrayList is in sorted order and doesn't contain any duplicates it means the given tree is a valid binary search tree otherwise not.

Complexity Analysis:

Time Complexity: O(n) for Traversing the nodes of tree + O(n) traversing the list. O(2n).

Space Complexity: O(n) for storing the nodes values.

Approach 2:

Maintain a pointer prev and keep comparing the current node value with prev. If at any stage prev node value becomes greater than or equal to current node value then it is not valid Binary Search Tree.

Code Implementation:

• Java

public class Solution {

// Constructor

static class Node {

int data;

Node left, right;

Node(int key) {

data = key;

left = right = null;

}

}

static Node prev = null; // keeps track of previous node

private static boolean isValidBST(Node root) {

// if root is null return true

if (root == null)

return true;

// go to left of node

if (!isValidBST(root.left)) {

return false;

}

// compare with prev node

if (prev != null && root.data <= prev.data)

return false;

// assign root value to prev

prev = root;

// go to right of node

if (!isValidBST(root.right)) {

return false;

}

// means condtions of BST is followed till now so return true

return true;

}

public static void main(String[] ans) {

/*

* Creating Binary Search Tree The created BST is same as in the above given

* figure (refer figure for reference)

*/

Node root = new Node(10);

root.left = new Node(8);

root.right = new Node(25);

root.left.left = new Node(5);

root.left.right = new Node(9);

root.right.left = new Node(22);

// calling the isValidBST method and printing the answer

System.out.println(isValidBST(root));

}

}

Output:

true

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in tree.

Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).