{"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":"

Inorder predecessor and successor for a given key in BST<\/span><\/strong><\/p>\n

I recently encountered with a question in an interview at e-commerce<\/a> company. The interviewer asked the following question:<\/p>\n

There is BST<\/a> given with root node with key part as integer<\/a> only. The structure<\/a> of each node is as follows:<\/p>\n

<\/div> 
struct Node{    int key;    struct Node *left, *right ;};<\/code><\/pre> <\/div>\n
\"inorder<\/p>\n[ad type=”banner”]\n
Following is the algorithm to reach the desired result. Its a recursive method:<\/strong><\/p>\n
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
Implementation of Python code:<\/span><\/h3>\n
 
 Python Programming<\/span> <\/div> 
# Python program to find predecessor and successor in a BST # A BST nodeclass Node:     # Constructor to create a new node    def __init__(self, key):        self.key  = key        self.left = None        self.right = None # This fucntion finds predecessor and successor of key in BST# It sets pre and suc as predecessor and successor respectivelydef findPreSuc(root, key):     # Base Case    if root is None:        return     # If key is present at root    if root.key == key:         # the maximum value in left subtree is predecessor        if root.left is not None:            tmp = root.left             while(tmp.right):                tmp = tmp.right             findPreSuc.pre = tmp          # the minimum value in right subtree is successor        if root.right is not None:            tmp = root.right            while(temp.left):                tmp = tmp.left             findPreSuc.suc = tmp          return     # If key is smaller than root's key, go to left subtree    if root.key > key :        findPreSuc.suc = root         findPreSuc(root.left, key)     else: # go to right subtree        findPreSuc.pre = root        findPreSuc(root.right, key) # A utility function to insert a new node in with given key in BSTdef insert(node , key):    if node is None:        return Node(key)     if key < node.key:        node.left = insert(node.left, key)     else:        node.right = insert(node.right, key)     return node  # Driver program to test above functionkey = 65 #Key to be searched in BST  """ Let us create following BST              50           \/     \\          30      70         \/  \\    \/  \\       20   40  60   80 """root = Noneroot = insert(root, 50)insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80); # Static variables of the function findPreSuc findPreSuc.pre = NonefindPreSuc.suc = None findPreSuc(root, key) if findPreSuc.pre is not None:    print "Predecessor is", findPreSuc.pre.key else:    print "No Predecessor" if findPreSuc.suc is not None:    print "Successor is", findPreSuc.suc.keyelse:    print "No Successor" # This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/span><\/h3>\n
Predecessor is 60\r\nSuccessor is 70<\/pre>\n","protected":false},"excerpt":{"rendered":"
python Programming Inorder predecessor and successor for a given key in BST – 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}]}}
You need to find the 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