Links
Go to my solution
Go to the question on LeetCode
My Thoughts
What Went Well
I was able to complete the problem after a few different approaches.
What Went Wrong
I was having a hard time putting my thoughts into code. Identifying the easiest and most efficient way to check each condition was difficult.
What I Learned
I have gained more experience practicing two essential algorithms and data structures.
Comments
The solution statistics for this problem are entirely broken because all the solutions are almost identical. This causes the same answer to sway from 95% to 5%.
Algorithm Description
Binary Search Tree - A sorted and ordered tree based on the root node. Subtrees to the left of ANY node are less than their parent, and those to the right are greater.
Depth-First Search - An algorithm for traversing a tree data structure. The algorithm begins at the root node and searches until it can not continue any deeper. Once at the deepest point, the algorithm works backward until all the nodes have been visited.
Visual Examples
Binary Search Tree, click to view
Depth-first search being performed on a tree, click to view
Solution Statistics
Time Spent Coding
25 minutes
Time Complexity
O(n) - We only need to iterate through each element in the binary search tree once, resulting in the O(n) time complexity.
Space Complexity
O(n) - Each recursive call has two variables, and the recursive function is called on each node, resulting in an O(2 * n) space complexity. Since big O ignores constant multiples of n, the “real” space complexity is O(n).
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def valid(lB,rB,root):
if not root: return True
# If the root's value is not between the left boundary (lB) and the right boundary (rB)
# then the binary search tree is not valid; return False
if not (root.val > lB and root.val < rB): return False
# If searching the left child, update the right boundary,
# because the entire subtree must be less than the current node's value
# If searching the right child, update the left boundary,
# because the entire subtree must be greater than the current node's value
return valid(lB,root.val,root.left) and valid(root.val,rB,root.right)
# Initially, there are no boundaries, so assign the largest values possible
return valid(float("-inf"),float("inf"),root)