{"id":27091,"date":"2018-01-03T21:20:30","date_gmt":"2018-01-03T15:50:30","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27091"},"modified":"2018-10-31T15:24:40","modified_gmt":"2018-10-31T09:54:40","slug":"python-programming-inorder-predecessor-successor-given-key-bst","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-inorder-predecessor-successor-given-key-bst\/","title":{"rendered":"Inorder predecessor and successor for a given key in BST"},"content":{"rendered":"<p><strong><span style=\"color: #003366;\">Inorder predecessor and successor for a given key in BST<\/span><\/strong><\/p>\n<p>I recently encountered with a question in an interview at <a href=\"https:\/\/www.wikitechy.com\/top10\/most-popular-ebusiness-websites\" target=\"_blank\" rel=\"noopener\">e-commerce<\/a> company. The interviewer asked the following question:<\/p>\n<p>There is <a href=\"https:\/\/www.wikitechy.com\/technology\/python-program-check-binary-tree-bst-not\/\" target=\"_blank\" rel=\"noopener\">BST<\/a> given with root node with key part as <a href=\"https:\/\/www.wikitechy.com\/forum\/d\/1155-solved-python-integer-incrementing-with\" target=\"_blank\" rel=\"noopener\">integer<\/a> only. The <a href=\"https:\/\/www.wikitechy.com\/tutorials\/c++\/c++-struct\" target=\"_blank\" rel=\"noopener\">structure<\/a> of each node is as follows:<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dstruct%20Node%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20struct%20Node%20*left%2C%20*right%20%3B%0A%7D%3B\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>You need to find the <a href=\"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-successor-binary-search-tree\/\" target=\"_blank\" rel=\"noopener\">inorder successor<\/a> and predecessor of a given key. In case the given key is not found in BST, then return the two values within which this key will lie.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-31786\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2018\/01\/inorder-successor-and-inorder-predecessor.png\" alt=\"inorder successor and inorder predecessor\" width=\"288\" height=\"258\" \/><\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Following is the algorithm to reach the desired result. Its a recursive method:<\/strong><\/p>\n<pre>Input: root node, key\r\noutput: predecessor node, successor node\r\n\r\n1. If root is NULL\r\n      then return\r\n2. if key is found then\r\n    a. If its left subtree is not null\r\n        Then predecessor will be the right most \r\n        child of left subtree or left child itself.\r\n    b. If its right subtree is not null\r\n        The successor will be the left most child \r\n        of right subtree or right child itself.\r\n    return\r\n3. If key is smaller then root node\r\n        set the successor as root\r\n        search recursively into left subtree\r\n    else\r\n        set the predecessor as root\r\n        search recursively into right subtree\r\n\r\n<\/pre>\n<h3 id=\"implementation-of-python-code\"><span style=\"color: #333300;\">Implementation of Python code:<\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20predecessor%20and%20successor%20in%20a%20BST%0A%20%0A%23%20A%20BST%20node%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20key)%3A%0A%20%20%20%20%20%20%20%20self.key%20%20%3D%20key%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20This%20fucntion%20finds%20predecessor%20and%20successor%20of%20key%20in%20BST%0A%23%20It%20sets%20pre%20and%20suc%20as%20predecessor%20and%20successor%20respectively%0Adef%20findPreSuc(root%2C%20key)%3A%0A%20%0A%20%20%20%20%23%20Base%20Case%0A%20%20%20%20if%20root%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%0A%20%0A%20%20%20%20%23%20If%20key%20is%20present%20at%20root%0A%20%20%20%20if%20root.key%20%3D%3D%20key%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20the%20maximum%20value%20in%20left%20subtree%20is%20predecessor%0A%20%20%20%20%20%20%20%20if%20root.left%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20root.left%20%0A%20%20%20%20%20%20%20%20%20%20%20%20while(tmp.right)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20tmp.right%20%0A%20%20%20%20%20%20%20%20%20%20%20%20findPreSuc.pre%20%3D%20tmp%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%23%20the%20minimum%20value%20in%20right%20subtree%20is%20successor%0A%20%20%20%20%20%20%20%20if%20root.right%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20root.right%0A%20%20%20%20%20%20%20%20%20%20%20%20while(temp.left)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20tmp.left%20%0A%20%20%20%20%20%20%20%20%20%20%20%20findPreSuc.suc%20%3D%20tmp%20%0A%20%0A%20%20%20%20%20%20%20%20return%0A%20%0A%20%20%20%20%23%20If%20key%20is%20smaller%20than%20root\u2019s%20key%2C%20go%20to%20left%20subtree%0A%20%20%20%20if%20root.key%20%3E%20key%20%3A%0A%20%20%20%20%20%20%20%20findPreSuc.suc%20%3D%20root%20%0A%20%20%20%20%20%20%20%20findPreSuc(root.left%2C%20key)%0A%20%0A%20%20%20%20else%3A%20%23%20go%20to%20right%20subtree%0A%20%20%20%20%20%20%20%20findPreSuc.pre%20%3D%20root%0A%20%20%20%20%20%20%20%20findPreSuc(root.right%2C%20key)%0A%20%0A%23%20A%20utility%20function%20to%20insert%20a%20new%20node%20in%20with%20given%20key%20in%20BST%0Adef%20insert(node%20%2C%20key)%3A%0A%20%20%20%20if%20node%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20Node(key)%0A%20%0A%20%20%20%20if%20key%20%3C%20node.key%3A%0A%20%20%20%20%20%20%20%20node.left%20%3D%20insert(node.left%2C%20key)%0A%20%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20node.right%20%3D%20insert(node.right%2C%20key)%0A%20%0A%20%20%20%20return%20node%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Akey%20%3D%2065%20%23Key%20to%20be%20searched%20in%20BST%0A%20%20%0A%22%22%22%20Let%20us%20create%20following%20BST%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2050%0A%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%5C%0A%20%20%20%20%20%20%20%20%20%2030%20%20%20%20%20%2070%0A%20%20%20%20%20%20%20%20%20%2F%20%20%5C%20%20%20%20%2F%20%20%5C%0A%20%20%20%20%20%20%2020%20%20%2040%20%2060%20%20%2080%20%0A%22%22%22%0Aroot%20%3D%20None%0Aroot%20%3D%20insert(root%2C%2050)%0Ainsert(root%2C%2030)%3B%0Ainsert(root%2C%2020)%3B%0Ainsert(root%2C%2040)%3B%0Ainsert(root%2C%2070)%3B%0Ainsert(root%2C%2060)%3B%0Ainsert(root%2C%2080)%3B%0A%20%0A%23%20Static%20variables%20of%20the%20function%20findPreSuc%20%0AfindPreSuc.pre%20%3D%20None%0AfindPreSuc.suc%20%3D%20None%0A%20%0AfindPreSuc(root%2C%20key)%0A%20%0Aif%20findPreSuc.pre%20is%20not%20None%3A%0A%20%20%20%20print%20%22Predecessor%20is%22%2C%20findPreSuc.pre.key%0A%20%0Aelse%3A%0A%20%20%20%20print%20%22No%20Predecessor%22%0A%20%0Aif%20findPreSuc.suc%20is%20not%20None%3A%0A%20%20%20%20print%20%22Successor%20is%22%2C%20findPreSuc.suc.key%0Aelse%3A%0A%20%20%20%20print%20%22No%20Successor%22%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)\u201d message=\u201dPython Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<h3 id=\"output\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>Predecessor is 60\r\nSuccessor is 70<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>python Programming Inorder predecessor and successor for a given key in BST &#8211; I recently encountered with a question in an interview at e-commerce company.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,1,4148],"tags":[70284,70277,80563,80542,80821,73310,72694,73309,80819,80551,80557,80820,80567,70268,80537,80548,80816,80574,80813,80541,70280,80817,80814],"class_list":["post-27091","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-coding","category-python","tag-binary-search-tree-in-data-structure","tag-binary-search-tree-java","tag-binary-search-tree-java-example-code","tag-binary-search-tree-pdf","tag-binary-search-tree-ppt","tag-binary-search-tree-program-in-c","tag-binary-search-tree-program-in-data-structure-using-c","tag-binary-search-tree-traversal","tag-binary-search-tree-traversal-example","tag-binary-search-tree-traversal-inorder-preorder-postorder-example","tag-binary-search-tree-with-example","tag-binary-search-trees-pdf","tag-binary-search-trees-ppt","tag-binary-tree","tag-binary-tree-algorithm-in-data-structure","tag-definition-of-binary-search-tree","tag-inorder-traversal","tag-program-of-binary-search-tree","tag-program-to-create-a-binary-tree","tag-root-binary","tag-search-tree","tag-threaded-binary-tree","tag-threaded-binary-tree-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27091","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27091"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27091\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27091"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27091"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27091"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}