Depth-First Search
Validate Binary Search Tree
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
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:
[2,1,4]
Output: true
Example 2:
Input:
[4,1,5,null,null,3,6]
Output: false. 3 is the the root node's right subtree, but it is less than the root node 4.
Explanation
Let's think about what it means for a binary tree to be a valid binary search tree. For a binary tree to be a valid binary search tree, the following conditions must be true:
- 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.
This definition is true for every subtree in the node.
We can use that definition to validate a binary search tree by having parents pass values down to their children. Let's say we are validating this binary search tree:
Based on the definition of a valid binary search tree, any value in the left subtree must be less than 4, but there is no limit to how small the values are.
So we can pass max = 4 and min = -inf to the left child as a range of valid values of the left subtree.
From there, for the subtree rooted at node 2:
The max value of any node in the left subtree 2 is 2, and the min value is still -inf.
Any value in the right subtree must be greater than the 2, but also less than 4 (the value of the root node). So we can pass max = 4 and min = 2 to the right child as a range of valid values of the right subtree.
We can visit each node in the tree, and have the parent pass down the range of valid values to their children in this fashion. If the current node's value falls outside of the valid range, we can return False immediately. If we reach the empty subtree, this means that we have not yet found an invalid node yet, and we can return True.
Return Values
If I'm at a node in the tree, what values do I need from my left and right children to tell if the current subtree is a valid binary search tree?
The current subtree is a valid binary search tree if:
- 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.
This tells me that each recursive call should return a boolean value indicating whether the current subtree is a valid binary search tree.
Base Case
An empty tree is a valid binary search tree.
Extra Work
The work that we need to do at each node is to check if the current node's value falls within the valid range. If it doesn't we can return False immediately.
Helper Functions
Since we need to pass the minimum and maximum values down to their children, we need to introduce a helper function to keep track of these values.
This helper function will introduce two parameters, min_ and max_, which represent the range of values that the current subtree's nodes can take on. The helper function will return a boolean value indicating whether the current subtree is a valid binary search tree.
When we recurse to our left child, we:
- 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.
When we recurse to our right child, we:
- 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.
Global Variables
The return value of the helper function matches the answer to the problem, so we don't need to use any global variables.
Solution
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.
Mark as read
Your account is free and you can post anonymously if you choose.