{"id":27314,"date":"2018-01-20T21:18:20","date_gmt":"2018-01-20T15:48:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27314"},"modified":"2018-10-31T10:46:35","modified_gmt":"2018-10-31T05:16:35","slug":"python-program-inorder-successor-binary-search-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-successor-binary-search-tree\/","title":{"rendered":"Inorder Successor in Binary Search Tree"},"content":{"rendered":"

Inorder Successor in Binary Search Tree:<\/strong><\/p>\n

In Binary Tree<\/a>, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal.<\/a><\/p>\n

<\/span>
\nIn Binary Search Tree<\/a>, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted<\/a> order.<\/p>\n

\"<\/p>\n

In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 12 and inorder successor of 14 is 20.<\/p>\n

\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n

Method 1 (Uses Parent Pointer)<\/strong><\/span><\/h3>\n

In this method, we assume that every node has parent pointer.<\/p>\n

The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.<\/p>\n

Input:<\/strong> node, root \/\/ node is the node whose Inorder successor is needed.
\noutput:<\/strong> succ \/\/ succ is Inorder successor of node.<\/p>\n

1)<\/strong> If right subtree<\/strong> of node is not NULL<\/strong>, then succ lies in right subtree. Do following.
\nGo to right subtree and return the node with minimum key value in right subtree.
\n2)<\/strong> If right subtree<\/strong> of node is NULL<\/strong>, then succ is one of the ancestors. Do following.
\nTravel up using the parent pointer until you see a node which is left child of it\u2019s parent. The parent of such a node is the succ.<\/p>\n

Implementation of Python Program:<\/strong><\/span><\/h3>\n

Note that the function to find InOrder Successor is highlighted (with gray background) in below code.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20the%20inroder%20successor%20in%20a%20BST%0A%20%0A%23%20A%20binary%20tree%20node%20%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.data%20%3D%20key%20%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%0Adef%20inOrderSuccessor(root%2C%20n)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Step%201%20of%20the%20above%20algorithm%0A%20%20%20%20if%20n.right%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20return%20minValue(n.right)%0A%20%0A%20%20%20%20%23%20Step%202%20of%20the%20above%20algorithm%0A%20%20%20%20p%20%3D%20n.parent%0A%20%20%20%20while(%20p%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20if%20n%20!%3D%20p.right%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20n%20%3D%20p%20%0A%20%20%20%20%20%20%20%20p%20%3D%20p.parent%0A%20%20%20%20return%20p%0A%20%0A%23%20Given%20a%20non-empty%20binary%20search%20tree%2C%20return%20the%20%0A%23%20minimum%20data%20value%20found%20in%20that%20tree.%20Note%20that%20the%0A%23%20entire%20tree%20doesn\u2019t%20need%20to%20be%20searched%0Adef%20minValue(node)%3A%0A%20%20%20%20current%20%3D%20node%0A%20%0A%20%20%20%20%23%20loop%20down%20to%20find%20the%20leftmost%20leaf%0A%20%20%20%20while(current%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20if%20current.left%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20current%20%3D%20current.data%0A%20%0A%20%20%20%20return%20current%0A%20%0A%20%0A%23%20Given%20a%20binary%20search%20tree%20and%20a%20number%2C%20inserts%20a%0A%23%20new%20node%20with%20the%20given%20number%20in%20the%20correct%20place%0A%23%20in%20the%20tree.%20Returns%20the%20new%20root%20pointer%20which%20the%0A%23%20caller%20should%20then%20use(%20the%20standard%20trick%20to%20avoid%20%0A%23%20using%20reference%20parameters)%0Adef%20insert(%20node%2C%20data)%3A%0A%20%0A%20%20%20%20%23%201)%20If%20tree%20is%20empty%20then%20return%20a%20new%20singly%20node%0A%20%20%20%20if%20node%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20Node(data)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%202)%20Otherwise%2C%20recur%20down%20the%20tree%0A%20%20%20%20%20%20%20%20if%20data%20%3C%3D%20node.data%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20insert(node.left%2C%20data)%0A%20%20%20%20%20%20%20%20%20%20%20%20node.left%20%3D%20temp%20%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.parent%20%3D%20node%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20insert(node.right%2C%20data)%0A%20%20%20%20%20%20%20%20%20%20%20%20node.right%20%3D%20temp%20%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.parent%20%3D%20node%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20return%20%20the%20unchanged%20node%20pointer%0A%20%20%20%20%20%20%20%20return%20node%0A%20%0A%20%0A%23%20Driver%20progam%20to%20test%20above%20function%0A%20%0Aroot%20%20%3D%20None%0A%20%0A%23%20Creating%20the%20tree%20given%20in%20the%20above%20diagram%20%0Aroot%20%3D%20insert(root%2C%2020)%0Aroot%20%3D%20insert(root%2C%208)%3B%0Aroot%20%3D%20insert(root%2C%2022)%3B%0Aroot%20%3D%20insert(root%2C%204)%3B%0Aroot%20%3D%20insert(root%2C%2012)%3B%0Aroot%20%3D%20insert(root%2C%2010)%3B%20%20%0Aroot%20%3D%20insert(root%2C%2014)%3B%20%20%20%20%0Atemp%20%3D%20root.left.right.right%20%0A%20%0Asucc%20%3D%20inOrderSuccessor(%20root%2C%20temp)%0Aif%20succ%20is%20not%20None%3A%0A%20%20%20%20print%20%22%5CnInorder%20Successor%20of%20%25d%20is%20%25d%20%22%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%25(temp.data%20%2C%20succ.data)%0Aelse%3A%0A%20%20%20%20print%20%22%5CnInorder%20Successor%20doesn\u2019t%20exist%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

Output:<\/strong><\/span><\/h3>\n

Inorder Successor of 14 is 20<\/em><\/p>\n

Time Complexity:<\/strong><\/span> O(h)<\/strong> where h is height of tree.<\/a><\/p>\n[ad type=\u201dbanner\u201d]\n

Method 2 (Search from root)<\/strong><\/span><\/h3>\n

Parent pointer<\/strong> is NOT needed in this algorithm. The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.<\/p>\n

Input:<\/strong> node, root \/\/ node is the node whose Inorder successor is needed.
\noutput:<\/strong> succ \/\/ succ is Inorder successor of node.<\/p>\n

Step 1:<\/strong><\/span> If right subtree<\/strong> of node is not NULL<\/strong>, then successor lies in right subtree. Do following.
\nGo to right subtree and return the node with minimum key value in right subtree.
\nStep 2:<\/strong> <\/span>If right subtree<\/strong> of node is NULL<\/strong>, then start from root and us search like technique. Do following.
\nTravel down the tree, if a node\u2019s data is greater than root\u2019s data then go right side, otherwise go to left side.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"

Python Program – In order Successor in Binary Search Tree – Binary Search Tree – In order Successor is NULL for the last node in In order traversal.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,80126,4148],"tags":[81419,81420,81412,81414,81413,81418,81415,81421,80862,81417,81416],"class_list":["post-27314","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binary-search-tree","category-python","tag-inorder-successor-in-bst","tag-inorder-successor-in-bst-java","tag-inorder-successor-in-bst-leetcode","tag-inorder-successor-without-parent-pointer","tag-inorder-traversal-in-bst","tag-postorder-successor","tag-preorder-successor","tag-python-program-inorder-successor-in-binary-search-tree","tag-successor-and-predecessor-in-binary-search-tree","tag-tree-predecessor-pseudocode","tag-what-is-successor-and-predecessor"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27314","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=27314"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27314\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}