Last active
October 11, 2018 01:43
-
-
Save lienista/75ffc952bc1021d909349b2cfc6e5ba8 to your computer and use it in GitHub Desktop.
(Algorithms in Javascript) // Leetcode #285. Inorder Successor in BST: 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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 4.6. Follow up - Successor: Write an algorithm to find the "next" node (i.e., in-order successor) | |
| // of a given node in a BST. Node do not have a link to its parent. | |
| import { BinaryTree } from "../helpers/tree.js"; | |
| const inorderSuccessor = (root, p) => { | |
| if(!p) return null; | |
| //if node has right subtree, get the min of left subtree. | |
| if(p.right) return findMinLeft(p.right); | |
| if(!p.right) return closestAncestorAsLeftChild(root, p) | |
| } | |
| function findMinLeft(node){ | |
| if(!node.left) return node; | |
| return findMinLeft(node.left); | |
| } | |
| function closestAncestorAsLeftChild(root, node){ | |
| if(!node) return null; | |
| let successor = null; | |
| let originalRoot = root; | |
| while(root){ | |
| if(node.value > root.value){ //record parent while traversing down tree | |
| root = root.right; | |
| } else if(node.value < root.value) { | |
| successor = root; | |
| root = root.left; | |
| } else { | |
| break; | |
| } | |
| } | |
| return successor; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment