{"id":9554,"date":"2017-02-11T22:29:29","date_gmt":"2017-02-11T22:29:29","guid":{"rendered":"http:\/\/www.softwareeverydayblog.com\/?p=9554"},"modified":"2020-10-11T01:27:50","modified_gmt":"2020-10-11T01:27:50","slug":"programming-problem-inorder-successor-in-bst","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=9554","title":{"rendered":"[Programming Problem] Inorder Successor in BST"},"content":{"rendered":"<p>Given a binary search tree and a node in it, find the in-order successor of that node in the BST.<\/p>\n<p>Note: If the given node has no in-order successor in the tree, return null.<\/p>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/inorder-successor-in-bst\/\" target=\"_blank\" rel=\"noopener noreferrer\">Problem Link<\/a>]<\/p>\n<ul>\n<li>If &#8216;P&#8217; >= current Node, go right as the next node is in the right sub tree<\/li>\n<li>If &#8216;P&#8217; <  current Node, go left as the next node is in the left sub tree<\/li>\n<li>On return of recursion we have a few choices.\n<ol>\n<li>Both the current node and return value are not a solution (i.e. <= P). Return null<\/li>\n<li>If one of the node&#8217;s is not a solution (i.e. <= P). Return the other!<\/li>\n<li>If both are a solution (i.e. both > P). Calculate the one with the smaller difference to P and return!<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n<p>Time complexity would be average case O(Log N), worst case O(N).<\/p>\n<pre lang=\"javascript\">\r\n\/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n *     this.val = val;\r\n *     this.left = this.right = null;\r\n * }\r\n *\/\r\n\/**\r\n * @param {TreeNode} root\r\n * @param {TreeNode} p\r\n * @return {TreeNode}\r\n *\/\r\nvar inorderSuccessor = function(root, p) {\r\n    let ret = inorderSuccessorFunc(root, p);\r\n    if (ret.val === Number.POSITIVE_INFINITY) return null;\r\n    else return ret;\r\n};\r\n\r\nvar inorderSuccessorFunc = function(root, p) {\r\n    \r\n    if ( root === null )\r\n        return new TreeNode(Number.POSITIVE_INFINITY);\r\n    \r\n    let ret = null;\r\n    if ( p.val >= root.val )\r\n        ret = inorderSuccessorFunc(root.right, p);\r\n    else\r\n        ret = inorderSuccessorFunc(root.left, p);\r\n    \r\n    \/\/ Answer: no candidate!\r\n    if ( root.val <= p.val &#038;&#038; ret.val <= p.val )\r\n        return null;\r\n    \r\n    \/\/ Answer: returned value from recursion\r\n    if ( root.val <= p.val &#038;&#038; ret.val > p.val )\r\n        return ret;\r\n    \r\n    \/\/ Answer: current root value is the answer\r\n    if ( root.val > p.val && ret.val <= p.val )\r\n        return root;\r\n    \r\n    \/\/ Answer: Both are potential answers\r\n    return Math.abs(ret.val-p.val) < Math.abs(root.val-p.val) \r\n        ? ret : root;\r\n\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note: If the given node has no in-order successor in the tree, return null. [Problem Link] If &#8216;P&#8217; >= current Node, go right as the next node is in the right sub tree If &#8216;P&#8217; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-9554","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/9554","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=9554"}],"version-history":[{"count":8,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/9554\/revisions"}],"predecessor-version":[{"id":11270,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/9554\/revisions\/11270"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=9554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=9554"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=9554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}