Is Binary Tree BST Editorial

Practice Problem Link: Is Binary Tree BST

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Every node in a binary search tree holds the following properties:

• The left subtree has nodes with values less than its own.
• The right subtree has nodes with values greater than its own.
• The left and right subtrees must also be Binary Search Trees.

Given the root node of a binary tree, determine whether it's a binary search tree.

Simple But Wrong Approach

A common but wrong idea is to simply check if the left child is smaller than the node and the right child is greater than the node for each node. 

This approach is wrong because even if a node satisfies the above condition but still there might be a node in the left subtree which is greater than the current node or a node in the right subtree which is less than the current node. Therefore, instead of checking only the left and right children, the whole left and right subtree of each node should be checked.

Naive Approach

The simple solution is the check for every node that the maximum value in the left subtree is less than the node and the minimum value in the right subtree is greater than the node. If this condition satisfies for every node then only the given binary tree is a BST.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int maxVal (Node* root) {
	int ans = INT_MIN;
	if(root->left != NULL) {
		ans = max(ans, maxVal(root->left));
	}
	ans = max(ans, root->data);
	if(root->right != NULL) {
		ans = max(ans, maxVal(root->right));
	}
	return ans;
}
int minVal (Node* root) {
	int ans = INT_MAX;
	if(root->left != NULL) {
		ans = min(ans, minVal(root->left));
	}
	ans = min(ans, root->data);
	if(root->right != NULL) {
		ans = min(ans, minVal(root->right));
	}
	return ans;
}
bool isBst(Node* root) {
    if (root == NULL) {
		return true;
	}
	if (root->left != NULL && maxVal(root->left) >= root->data) {
		return false;
	}
	if (root->right != NULL && minVal(root->right) <= root->data) {
		return false;
	}
	if (isBst(root->left) == false || isBst(root->right) == false) {
		return false;
	}
	return true;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	int maxVal (Node root) {
		int ans = Integer.MIN_VALUE;
		if(root.left != null) {
			ans = Math.max(ans, maxVal(root.left));
		}
		ans = Math.max(ans, root.data);
		if(root.right != null) {
			ans = Math.max(ans, maxVal(root.right));
		}
		return ans;
	}
	int minVal (Node root) {
		int ans = Integer.MAX_VALUE;
		if(root.left != null) {
			ans = Math.min(ans, minVal(root.left));
		}
		ans = Math.min(ans, root.data);
		if(root.right != null) {
			ans = Math.min(ans, minVal(root.right));
		}
		return ans;
	}
	boolean isBst(Node root) {
	    if (root == null) {
			return true;
		}
		if (root.left != null && maxVal(root.left) >= root.data) {
			return false;
		}
		if (root.right != null && minVal(root.right) <= root.data) {
			return false;
		}
		if (isBst(root.left) == false || isBst(root.right) == false) {
			return false;
		}
		return true;
	}
}

Optimal Approach

The idea of the optimal solution is quite similar to the naive solution. But here tree traversal will be done only once.

• Traverse every node recursively and for each node keep the track of the range in which the node must lie. (i.e from minVal to maxVal).
• If all the nodes are in the correct range then return true otherwise return false.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
bool checkBst(Node* root, int minVal, int maxVal) {
	if(root == NULL) {
		return true;
	}
	if (root->data <= minVal || root->data >= maxVal) {
		return false;
	}
	if(checkBst(root->left, minVal, root->data) && checkBst(root->right, root->data, maxVal)) {
		return true;
	}
	return false;
}
bool isBst(Node* root) {
	return checkBst(root, INT_MIN, INT_MAX);
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	boolean checkBst(Node root, int minVal, int maxVal) {
		if(root == null) {
			return true;
		}
		if (root.data <= minVal || root.data >= maxVal) {
			return false;
		}
		if(checkBst(root.left, minVal, root.data) && checkBst(root.right, root.data, maxVal)) {
			return true;
		}
		return false;
	}
	boolean isBst(Node root) {
	    return checkBst(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
}