Check if a tree is a BST or not
M2P FintechThe problem
Given the root node of a binary tree. Return true if the given binary tree is a binary search tree(BST) else false.
A valid BST is defined as follows:
-
The left subtree of a node contains only nodes with key strictly less than the node's key.
-
The right subtree of a node contains only nodes with key strictly greater than the node's key.
-
Both the left and right subtrees must also be binary search trees.
Input : root = [5, 3, 6, 2, 4, null, 7] Output : true Explanation : Below is image of the given tree.
Input : root = [5, 3, 6, 4, 2, null, 7] Output : false Explanation : ****Below is image of the given tree. The node 4 and node 2 violates the BST rule of smaller to left and larger to right.
Input : root = [2, 1, 3]
- 1 <= Number of Nodes <= 104
- -231 <= Node.val <= 231 - 1
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution{
public:
bool isBST(TreeNode* root){
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public boolean isBST(TreeNode root) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def isBST(self, root):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
isBST(root) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int data;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.data = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public bool IsBST(TreeNode root) {
}
}go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Data int
* Left *TreeNode
* Right *TreeNode
* }
*/
func IsBST(root *TreeNode) bool {
//your code goes here
}Stuck? Show a way to structure it+
- 01Carry an exclusive lower and upper bound into each recursive call.
- 02Require every node to lie strictly within its bounds.
- 03Recurse left with the node as upper bound.
- 04Recurse right with the node as lower bound.
Reference answer
Then expect these follow-ups
How would you validate iteratively?
Tests: explicit stack
How do duplicate-key BST rules change the bounds?
Tests: spec interpretation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question