Validate Binary Search Tree
Statement
Given the root of a binary tree, check whether it’s a valid binary search tree (BST).
Constraints
- -10⁴ ≤
node.data≤ 10⁴ - 1 ≤ number of nodes ≤ 500
Solution
"""
production algorithm
"""
class Solution:
def validate_bst(self, root):
"""
time complexity O(n)
space complexity O(n)
"""
prev, result = [float("-inf")], [True]
self.validate_bst_helper(root, prev, result)
return result[0]
def validate_bst_helper(self, root, prev, result):
"""
time complexity O(n)
space complexity O(n)
"""
if root is None:
return
self.validate_bst_helper(root.left, prev, result)
result[0], prev[0] = result[0] and prev[0] < root.data, root.data
self.validate_bst_helper(root.right, prev, result)"""
unit tests
"""
from unittest import TestCase
from algorithms.dfs.validate_binary_search_tree.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode
class SolutionTestCase(TestCase):
def test_valid_bst(self):
# Given
root = BinaryTreeNode(9)
root.left = BinaryTreeNode(3)
root.right = BinaryTreeNode(11)
root.left.left = BinaryTreeNode(-1)
root.left.right = BinaryTreeNode(6)
root.right.left = BinaryTreeNode(10)
root.right.right = BinaryTreeNode(16)
root.right.right.right = BinaryTreeNode(18)
solution = Solution()
# When
actual = solution.validate_bst(root)
# Then
expected = True
self.assertEqual(actual, expected)
def test_invalid_bst(self):
# Given
root = BinaryTreeNode(9)
root.left = BinaryTreeNode(3)
root.right = BinaryTreeNode(11)
root.left.left = BinaryTreeNode(-1)
root.left.right = BinaryTreeNode(6)
root.right.left = BinaryTreeNode(12)
root.right.right = BinaryTreeNode(16)
root.right.right.right = BinaryTreeNode(18)
solution = Solution()
# When
actual = solution.validate_bst(root)
# Then
expected = False
self.assertEqual(actual, expected)Strategy
Depth First Search.
Explanation
The algorithm tracks two pieces of information, the value of the previous node, and the result of the algorithm seen so far. Then, an inorder traversal of the binary tree occurs. At the root, the previous value and the current value are compared, and then the previous value is updated. At the end of traversal , the result of the algorithm says whether the binary tree is a valid binary search tree.
Time Complexity
Every node of the binary tree is visited once. Therefore, the time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.
Space Complexity
In the case of a degenerate tree, the depth of recursion of inorder traversal reaches n. Therefore, the auxiliary space complexity of the algorithm is O(n).
