Traverse the tree in natural order and test if each node is between the previous and the next node. Properly detect duplicate values. If a wrong sub-tree is encountered immediately stop the script and indicate the error.<\/p>\n
See code below<\/p>\n
<\/p>\n
# python3\r\n\r\nimport sys, threading\r\nsys.setrecursionlimit(10**6) # max depth of recursion\r\nthreading.stack_size(2**27) # new thread will get stack of such size\r\n\r\nclass TreeOrders:\r\n def __init__(self):\r\n \"\"\"We can't assume a proper BST description, only a proper\r\n binary tree. In order to use the BST class we have to\r\n generate and assign keys while creating the tree.\r\n The 'values' will be assigned as a new 'label' field.\r\n The first node is going to be the initial root.\r\n \"\"\"\r\n n = int(input())\r\n self.nodes = [list(map(int, sys.stdin.readline().split())) for i in range(n)]\r\n\r\n def value(self, i):\r\n \"\"\"Return the value (key) of the node at index i.\"\"\"\r\n return self.nodes[i][0]\r\n\r\n def left(self, i):\r\n \"\"\"Return the index of the left child of node at index i\r\n or None if the node doesn't have a left child.\"\"\"\r\n result = self.nodes[i][1]\r\n if result == -1:\r\n return None\r\n else:\r\n return result\r\n\r\n def right(self, i):\r\n \"\"\"Return the index of the right child of node at index i\r\n or None if the node doesn't have a right child.\"\"\"\r\n result = self.nodes[i][2]\r\n if result == -1:\r\n return None\r\n else:\r\n return result\r\n\r\n def is_bst(self, index=0):\r\n \"\"\"Traverse the tree in \"natural\" order and test if each node\r\n is between the previous and the next node.\r\n Properly detect duplicate values.\r\n If a wrong subtree is encountered immediately report and stop the script.\"\"\"\r\n # find children\r\n l = self.left(index)\r\n r = self.right(index)\r\n # get left and right subtrees (if present)\r\n left = self.is_bst(index=l) if l else []\r\n right = self.is_bst(index=r) if r else []\r\n if left and self.value(left[-1]) >= self.value(index) or right and self.value(right[0]) < self.value(index):\r\n fail()\r\n return left[0::-1] + [index] + right[0::-1]\r\n\r\ndef fail():\r\n print(\"INCORRECT\")\r\n sys.exit()\r\n\r\ndef main():\r\n tree = TreeOrders()\r\n if len(tree.nodes) == 0 or tree.is_bst():\r\n print(\"CORRECT\")\r\n\r\nthreading.Thread(target=main).start()<\/pre>\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Binary Search Tree Traverse the tree in natural order and test if each node is between the previous and the next node. Properly detect duplicate values. If a wrong sub-tree is encountered immediately stop the script and indicate the error. See code below<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28,30,34],"series":[],"class_list":["post-151","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python","tag-code","tag-binary-search-tree"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/151","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=151"}],"version-history":[{"count":1,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/151\/revisions"}],"predecessor-version":[{"id":152,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/151\/revisions\/152"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=151"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}