Learn Code
Depth-First Search
Greedy Algorithms
Depth-First Search
Validate Binary Search Tree
medium
DESCRIPTION (credit Leetcode.com)
Given the root of a binary, write a recursive function to determine if it is a valid binary search tree.
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A tree is a BST if the following conditions are met:
- Every node on the left subtree has a value less than the value of the current node.
- Every node on the right subtree has a value greater than the value of the current node.
- The left and right subtrees must also be valid BSTs.
Example 1:
Input:
Output: true
Example 2:
Input:
Output: false. 3 is the the root node's right subtree, but it is less than the root node 4.
Explanation
- Every node in the left subtree of the root node must have a value less than the value of the root node.
- Every node in the right subtree of the root node must have a value greater than the value of the root node.
- The left subtree is a valid binary search tree.
- The right subtree is a valid binary search tree.
- And the value of the current node falls within the valid range.
- Pass the current node's value as the new max_ value, since the left child's value must be less than the current node's value. min_ remains the same.
- Pass the current node's value as the new min_ value, since the right child's value must be greater than the current node's value. max_ remains the same.
Solution
class Solution:def validateBST(self, root):def dfs(node, min_, max_):# base caseif node is None:return True# check if the current node's value is within the valid rangeif node.val <= min_ or node.val >= max_:return Falsereturn dfs(node.left, min_, node.val) and dfs(node.right, node.val, max_)return dfs(root, float('-inf'), float('inf'))
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N) where N
is the number of nodes in the binary tree. We visit each node via each recursive call to dfs
exactly once. Each recursive call does a constant amount of work.
Space Complexity: O(N) where N
is the number of nodes in the binary tree, for the space that it takes to allocate each recursive call frame on the call stack.
Login to track your progress
Your account is free and you can post anonymously if you choose.