You are viewing a single comment's thread. Return to all comments →
A variation where a stack is used instead of recursion. I do not fancy recursion in Python as the maximum recursion depth is about 1000 per default. With the stack (a deque could also be used), you avoid a potential recursion limit error.
With the stack, no helper method is needed either.
if root is None:
stack = [(float('-inf'), root, float('+inf'))]
mind, node, maxd = stack.pop()
if not (mind < node.data < maxd):
if node.left is not None:
stack.append((mind, node.left, node.data))
if node.right is not None:
stack.append((node.data, node.right, maxd))
Wow, I was impressed with a few other submissions, but this, this is really good. +1
Impressive! Am I right to say that this is an O(n) solution?
I'm really bad at this kind of stuff but I'm actually going to throw caution to the wind and say no because you're appending to the input at the same time as looping through it. On the first itteration of the while loop you append two new items which on the next itteration will need to be pop-ed off and then possibly add another two calls.
Please correct me if I'm wrong, I'd be interested to hear from a computer scientist on this one.
This dynamic programming allows to skip reqursion, which is high performance gain.