LeetCode 98. Validate Binary Search Tree [Algorithm + Code Explained ] Best Solution

Показать описание

One of the most frequently asked coding interview questions on Trees in companies like Google, Facebook, Amazon, LinkedIn, Microsoft, Uber, Apple, Adobe etc.

LeetCode : Validate Binary Search Tree

Question : Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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:

2
/ \
1 3

Input: [2,1,3]
Output: true
Example 2:

5
/ \
1 4
/ \
3 6

Input: [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.

Рекомендации по теме

Комментарии

Hello Di,
You are doing prolific job to add values in lives of young engineers like us.
It will definitely make the job seekers get a better grip over these important topics.
I request you to make a session which would help Upcoming Engineers to better understand what computer science engineering is, so that they could decide what early steps to take on to make a good career.

Key Points i think to guide on
- Various streams (Technologies), sub domains falling under CSE.
- Trending technologies & Must have skill sets.
- How one can identify whether to go for coding, testing, networking etc.
- Foundation subjects which are must for firm underpinning.
- Few things (facts) to eliminate code Phobia.
(P.S Please add something left out)

It can be the "Guiding Light" for individuals coming into CSE & will help them in not going off the tracks.

Thanks from the Side of all learners.
Regards

manastiwari

Hi Jayati,

Thanks for doing a great job in helping people tackle quality problems for interviews.

One query on this problem:
- My immediate thought after seeing the question was to do a inorder traversal and break whenever sorting order breaks. Why was this not the default approach when you try to solve this.

- The approach you have mentioned seems like a "top-down" approach where parent checks itself and propogates its values as "min" and "max". Let's take the root. The root needs to know that max of its left-subtree before it declares itself as valid. (ie root must be > left-max). Kindly let me know how does this happen in your algorthm.

computer

I 'm a software Ingineer (woman) ans i wish i will be as competent as you! keep on the good work and thank u for your help

radiabairi

Why did we use the wrapper class Integer for min and max instead of just using int?

rajatkaushik

Ma'am this code is not run in c++ language.

sohaibmansuri

class Solution {
public:
bool isValidBST(TreeNode* root) {
return checkBST(root, NULL, NULL);
}
bool checkBST(TreeNode* root, int minval, int maxval){
if(root==NULL){
return true;
}
if((minval!=NULL && root->val<=minval) ||(maxval!=NULL && root->val>=maxval)){
return false;
}
return checkBST(root->left, minval, root->val) && checkBST(root->right, root->val, maxval);
}
};

sohaibmansuri

LeetCode 98. Validate Binary Search Tree [Algorithm + Code Explained ] Best Solution

Validate Binary Search Tree - Depth First Search - Leetcode 98

Validate Binary Search Tree - Leetcode 98

LeetCode 98. Validate Binary Search Tree (Algorithm Explained)

LeetCode 98. Validate Binary Search Tree - Interview Prep Ep 69

Validate Binary Search Tree - Leetcode 98

Validate Binary Search Tree (LeetCode 98) | Full solution with animations and visuals

Validate Binary Search Tree - Leetcode 98

Validate Binary Search Tree | Live Coding with Explanation | Leetcode - 98

[Java] Leetcode 98. Validate Binary Search Tree [Binary Search Tree #3]

Leetcode - Validate Binary Search Tree (Python)

Validate Binary Search Tree - Leetcode 98 - Trees (Python)

Validate Binary Search Tree - LeetCode 98 - JavaScript

Leetcode 98: Validate Binary Search Tree VISUALIZED

Validate Binary Search Tree | Leetcode 98

FAANG BST QUESTION! | Validate Binary Search Tree - Leetcode 98

Leetcode Q98: Validate Binary Search Tree Solution VISUALIZED

LeetCode Interview Problem | Validate Binary Search Tree

Validate Binary Search Tree

Leetcode 98: Validate Binary Search Tree

Leetcode 98 Validate Binary Search Tree (Java)

Leetcode 98 - Validate Binary Search Tree (JAVA Solution Explained!)

Validate Binary Search Tree - LeetCode 98 - Coding Interview Questions

Validate Binary Search Tree Leetcode Recursion 3 line solution

Software Engineer/Developer Interview Question: 98. Validate Binary Search Tree