Validate Binary Search Tree

Validate Binary Search Tree#


Question Number Difficulty Tag Tag Tag Tag

Problem#

A clear and concise statement of the problem.

Example#

1tree_values = [4, 2, 1, None, None, 3, None, None, 7, None, None]
2root = build_binary_tree_from_list_preorder(tree_values)
3print_binary_tree(root, node_info=lambda n: (str(n.value), n.left, n.right), is_top=True)

    4
   / \
  2   7
 / \
1   3

Intuition#

We will do the easiest way that minimizes the changes to the binary search tree.

An important observation is for any binary search tree, and consider that it has \(m\) leaf nodes \(l_1, l_2, \ldots, l_m\), then for the target node \(t\) that is ready to be inserted, we can insert \(t\) into any of the leaf nodes \(l_1, l_2, \ldots, l_m\) and the resulting binary search tree will be the same.

Without loss of generality, we will insert the target node \(t\) into the leaf node \(l_1\). Then either \(g(t) < g(l_1)\) or \(g(t) > g(l_1)\). So if \(g(t) < g(l_1)\), then we will insert \(t\) into the left child of \(l_1\), and if \(g(t) > g(l_1)\), then we will insert \(t\) into the right child of \(l_1\).

Assumptions#

List of any assumptions made in the problem solving process.

Constraints#

What are the Constraints for?#

Explanation of the constraints and their impact on the problem and solution.

Test Cases#

Set of test cases for validating the solution.

Edge Cases#

Discussion of any potential edge cases in the problem.

Walkthrough / Whiteboarding#

Detailed walkthrough of the problem-solving process.

Theoretical Best Time Complexity#

Discussion of the theoretical best time complexity for this problem.

Theoretical Best Space Complexity#

Discussion of the theoretical best space complexity for this problem.

Space-Time Tradeoff#

Analysis of the tradeoff between space and time complexity for the problem.

Solution (Potentially Multiple)#

Intuition#

Brief explanation of the core ideas or insights that form the basis for the solution.

Visualization#

Visual representation of the problem and solution (if applicable).

Algorithm#

Pseudocode#

Mathematical Representation#

Claim#

Statement claiming the correctness of the algorithm.

Proof#

Proof showing the correctness of the algorithm.

Implementation#

 1class Solution:
 2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
 3        nodes = []
 4
 5        def dfs_inorder(root, nodes):
 6            if not root:
 7                return None
 8
 9            dfs_inorder(root.left, nodes)
10            nodes.append(root.val)
11            dfs_inorder(root.right, nodes)
12            return nodes
13
14        nodes = dfs_inorder(root, nodes)
15
16        min_value = float("-inf")
17        for node in nodes:
18            if node > min_value:
19                min_value = node
20            else:
21                return False
22        return True

 1class Solution:
 2    def isValidBST(self, root: TreeNode) -> bool:
 3        def validate(node, lower_limit=float('-inf'), upper_limit=float('inf')):
 4            if not node:
 5                return True
 6
 7            if node.val <= lower_limit or node.val >= upper_limit:
 8                return False
 9
10            left_subtree_is_valid = validate(node.left, lower_limit, node.val)
11            right_subtree_is_valid = validate(node.right, node.val, upper_limit)
12
13            return left_subtree_is_valid and right_subtree_is_valid
14
15        return validate(root)

Tests#

Set of tests for validating the algorithm.

Time Complexity#

Analysis of the time complexity of the solution.

Space Complexity#

Input Space Complexity#

Analysis of the space complexity of the input.

Auxiliary Space Complexity#

Analysis of the space complexity excluding the input and output space.

Total Space Complexity#

Analysis of the total space complexity of the solution.

References and Further Readings#