In this post, we are going to solve the 98. Validate Binary Search Tree problem of Leetcode. This problem 98. Validate Binary Search Tree is a Leetcode medium level problem. Let’s see the code, 98. Validate Binary Search Tree – Leetcode Solution.
Problem
Given the root
of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1 :
Input: root = [2,1,3]
Output: true
Example 2 :
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints
- The number of nodes in the tree is in the range
[1, 104]
. -231 <= Node.val <= 231 - 1
Now, let’s see the code of 98. Validate Binary Search Tree – Leetcode Solution.
Validate Binary Search Tree – Leetcode Solution
98. Validate Binary Search Tree – Solution in Java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { if(root == null) return true; TreeNode curr = root; TreeNode prev = null; Stack<TreeNode> stack = new Stack<>(); while(curr != null || !stack.isEmpty()){ while(curr != null){ stack.push(curr); curr = curr.left; } curr = stack.pop(); if(prev != null && curr.val <= prev.val) return false; prev = curr; curr = curr.right; } return true; } }
98. Validate Binary Search Tree – Solution in C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { long pre = LONG_MIN; stack<TreeNode*> todo; while (root || !todo.empty()) { while (root) { todo.push(root); root = root -> left; } root = todo.top(); todo.pop(); if (root -> val <= pre) { return false; } pre = root -> val; root = root -> right; } return true; } };
98. Validate Binary Search Tree – Solution in Python
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isValidBST(self, root): pre, stack = None, [] while True: while root: stack.append(root) root = root.left if not stack: return True node = stack.pop() if pre and pre.val >= node.val: return False pre = node root = node.right
Note: This problem 98. Validate Binary Search Tree is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.