Created
October 11, 2018 00:35
-
-
Save lienista/9465e1f61b28092e021ae8d74f09a92e to your computer and use it in GitHub Desktop.
(Algorithms in Javascript) CTCI 4.6. Inorder Successor: Write an algorithm to find the "next" node (i.e., in-order successor) of a given node in a BST. You may assume that each node has a link to its parent.
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. Successor: Write an algorithm to find the "next" node (i.e., in-order successor) | |
| // of a given node in a BST. You may assume that each node has a link to its parent. | |
| import { BinaryTree } from "../helpers/tree.js"; | |
| const inOrderSuccessor = (root) => { | |
| if(!root) return null; | |
| //if node has right subtree, get the min of left subtree. | |
| if(root.right) return findMinLeft(root.right); | |
| if(!root.right) return closestAncestorAsLeftChild(root) | |
| } | |
| function findMinLeft(node){ | |
| if(!node.left) return node; | |
| return findMin(node.left); | |
| } | |
| function closestAncestorAsLeftChild(node){ | |
| if(!node || !node.parent) return null; | |
| if(node.parent.value > node.value) return node.parent; //node is left child | |
| return closestAncestorAsLeftChild(node.parent); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment