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.
parents = 
sides = 
# 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:
if root.data <= parents[i].data:
# 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.data < root.data:
status = checkBST(root.left)
if status == False:
if root.right.data > root.data:
status = checkBST(root.right)
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.