We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I never know if I'm supposed to/"allowed" to create secondary functions to use within the function they want me to define.
I love the simplicity of using just the maximum and minimum of earlier parent nodes; I'm not 100% sure there wouldn't be any issues, but conceptually/theoretically (as far as I can see/think) it makes sense.
Since I took a somewhat different approach to anything I've seen here, I thought I'd include it here for anyone interested. I also welcome feedback, if anyone has anything to point out about what could be improved.
parents = []
sides = []
def checkBST(root):
# compare current node to all the parents
# (don't forget we can't have equal nodes either!)
for i in range(len(parents)):
if sides[i] == 'left':
if root.data >= parents[i].data:
return False
else:
if root.data <= parents[i].data:
return False
# compare current node to its children & go deeper
status = True
# I use this to check the left side and only return False
# if we know it's not a BST, but if it is so far,
# we want to continue and look on the right side
if root.left:
if root.left.data < root.data:
parents.append(root)
sides.append('left')
status = checkBST(root.left)
parents.pop()
sides.pop()
if status == False:
return status
else:
return False
if root.right:
if root.right.data > root.data:
parents.append(root)
sides.append('right')
status = checkBST(root.right)
parents.pop()
sides.pop()
else:
return False
return status
The idea is to note which direction I've gone down from a parent, so I know whether that node needs to be larger/smaller than each respective parent. I think the overall time complexity should be n * log n...right? (n from going through each node, and log n from each node's looking at the parents.) Again, I welcome any feedback on this approach.
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
I never know if I'm supposed to/"allowed" to create secondary functions to use within the function they want me to define.
I love the simplicity of using just the maximum and minimum of earlier parent nodes; I'm not 100% sure there wouldn't be any issues, but conceptually/theoretically (as far as I can see/think) it makes sense.
Since I took a somewhat different approach to anything I've seen here, I thought I'd include it here for anyone interested. I also welcome feedback, if anyone has anything to point out about what could be improved.
The idea is to note which direction I've gone down from a parent, so I know whether that node needs to be larger/smaller than each respective parent. I think the overall time complexity should be n * log n...right? (n from going through each node, and log n from each node's looking at the parents.) Again, I welcome any feedback on this approach.