# Python version based on inorder traversal

• ``````# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param root, a tree node
# @return a boolean
# 7:38
def isValidBST(self, root):
output = []
self.inOrder(root, output)

for i in range(1, len(output)):
if output[i-1] >= output[i]:
return False

return True

def inOrder(self, root, output):
if root is None:
return

self.inOrder(root.left, output)
output.append(root.val)
self.inOrder(root.right, output)``````

• my solution is like yours, and using sorted and set to validate length and order if correct

``````class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""

self.res = list()
self.validation(root)

return self.res == sorted(self.res) and len(set(self.res)) == len(self.res)

def validation(self, root):

if not root:
return
else:
self.validation(root.left)
self.res.append(root.val)
self.validation(root.right)``````

• I did almost the same as yours. But my concern is that this solution is quite slow.. Yes, O(n) guaranteed, but do we have chance to "short circuit" as soon as we find the incorrect ordering while doing the inOrder()? I'm just curious why other people getting much better running time than this.

• @WeilanYang
add a test at the start of inOrder()

``````if len(output) > 1 and output[-1] <= output[-2]:
return
``````

• Here's a similar solution but with O(1) space, where you only check if the current element is greater than the previous element, and you break out of checking the rest if this is False.

``````class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.isBSTHelper(root, [])

def isBSTHelper(self, root, prev=[]):
if not root:
return True
if not self.isBSTHelper(root.left, prev):
return False
if not prev:
prev.append(root.val)
elif root.val <= prev[0]:
return False
prev[0] = root.val
if not self.isBSTHelper(root.right, prev):
return False
return True
``````

• @yorkshire
Your suggestion doesn't really improve the solution, because it will travel through the other part of the tree anyway.
@WeilanYang
Here is my solution according to your suggestion:

``````    def isValidBST(self, root):
self.res = []
return self.inOrder(root)

def inOrder(self, root):
if not root: return True
if not self.inOrder(root.left): return False
if len(self) and self.res[-1] >= root.val: return False
self.res.append(root.val)
return self.inOrder(root.right)``````

• @lee215 correct my mistake. below version stops traversal and only stores the previous node value not the whole tree

``````class Solution(object):
def isValidBST(self, root):
self.correct = True
self.prev = float('-inf')
self.inorder(root)
return self.correct

def inorder(self, node):
if not node or not self.correct:    # return if already found out of order
return

self.inorder(node.left)
if node.val <= self.prev:
self.correct = False
return          # halt exploration
self.prev = node.val
self.inorder(node.right)
``````

• My solution, also based on inorder traversal :)

``````class Solution(object):
def isValidBST(self, root):
if not root:return True
stack=[]
res=[]
while root or stack:
if root:
stack.append(root)
root=root.left
else:
root=stack.pop()
res.append(root.val)
root=root.right
if res==sorted(res) and len(res)==len(set(res)):
return True
else:return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.