98. Validate Binary Search Tree
Validate Binary Search Tree (LeetCode 98) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Inorder Traversal subpattern.
How to solve Validate Binary Search Tree
Validate Binary Search Tree is a Inorder Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master inorder traversal for BST validation and kth element problems. Produces sorted order in BST.
Work towards the solution in these steps:
- Recall the properties of a binary search tree and consider how traversing the tree can help verify these properties.
- Think about using a depth-first traversal to explore nodes in a specific order that relates to the BST property.
- An inorder traversal of a BST yields nodes in ascending order; how could this characteristic help validate the tree?
The reference solution runs in O(n) time and O(1) space.
The Validate Binary Search Tree solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree.
Reported in interviews at Amazon, Apple, Asana, Bloomberg, Facebook, Google, Microsoft, Oracle, VMware.
How to practise Validate Binary Search Tree on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Validate Binary Search Tree in the code editor, or read the Validate Binary Search Tree editorial for a worked solution with its approach and complexity analysis.
Where Validate Binary Search Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Inorder Traversal subpattern
- The full DSA patterns sheet
Problems related to Validate Binary Search Tree
Other problems that use the same Recursive Inorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Search Tree Iterator — Medium, same subpattern
- Binary Tree Inorder Traversal — Easy, same subpattern
- Delete Node in a BST — Medium, same subpattern
- Find Mode in Binary Search Tree — Easy, same subpattern
- Kth Smallest Element in a BST — Medium, same subpattern
- Minimum Absolute Difference in BST — Easy, same subpattern
Validate Binary Search Tree FAQ
What is the LeetCode number of Validate Binary Search Tree?
Validate Binary Search Tree is LeetCode problem 98, rated Medium.
What pattern is used to solve Validate Binary Search Tree?
Validate Binary Search Tree is a Inorder Traversal problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Inorder Traversal subpattern.
What is the time complexity of Validate Binary Search Tree?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Validate Binary Search Tree?
Validate Binary Search Tree has been reported in interviews at Amazon, Apple, Asana, Bloomberg, Facebook, Google, Microsoft, Oracle, VMware.