The goal is, given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
The problem setting is the same as here
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
level=[root]
while level:
for k in level:
if k.left:
if k.left >= k.val:
return False
if k.right:
if k.right <= k.val:
return False
level=[leaf for n in level for leaf in (n.left,n.right) if leaf]
return True
The above solution could not work for the case [2,1,3] which I believe the bug is located at this part after some debugging processes
if k.left:
if k.left >= k.val:
return False
What is wrong with it? Thanks in advance for any help.
CodePudding user response:
There are a couple of issues with your code:
- In the lines
if k.left >= k.val:
andif k.right <= k.val:
you are comparing nodes to values, which I assume is not your intention. - Assuming the above is corrected, the general logic only compares the values of children with those of their immediate parents, which is not enough to satisfy the part of the problem specification stating, "The left subtree of a node contains only nodes with keys less than the node's key", or the symmetrical part of the spec regarding the right subtree. To satisfy this, you need to track the ancestral bounds with which a given node's
val
attribute must comply.
Here's an example of a modification to your code that would work as an iterative solution:
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
level=[(root,None,None)]
while level:
level2 = []
for k,floor,ceil in level:
if k.left:
if k.left.val >= k.val or floor is not None and k.left.val <= floor:
return False
level2.append((k.left,floor,k.val))
if k.right:
if k.right.val <= k.val or ceil is not None and k.right.val >= ceil:
return False
level2.append((k.right,k.val,ceil))
level = level2
return True
t = TreeNode(2, TreeNode(1), TreeNode(3))
x = Solution()
print(x.isValidBST(t))
Ouput:
True
Explanation:
- instead of storing each non-null node at a given level, we store a tuple for each such node including the node itself as well as
floor
andceil
values (set to None forroot
) that will allow us to carry forward (or downward as we descend the levels of the tree) the bounds to which a given subtree must conform. - When we traverse leftward via a non-null
left
attribute, we overwriteceil
with the immediate parent'sval
attribute, and for rightward traversal via a non-nullright
attribute we overwritefloor
.