Last active
March 8, 2024 19:44
-
-
Save rcaloras/36f9e5f94f4334e0827c5b52ec0d8115 to your computer and use it in GitHub Desktop.
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
class BinaryTreeNode { | |
BinaryTreeNode left; | |
BinaryTreeNode right; | |
int value; | |
} | |
public static BinaryTreeNode findInorderSuccessor(BinaryTreeNode root, int value) { | |
if (root == null) { | |
throw new IllegalArgumentException("Root cannot be null"); | |
} | |
// Find the node for value in our tree | |
// If we're given the node instead of a | |
// value this whole block can be omitted. | |
BinaryTreeNode find = null; | |
BinaryTreeNode n = root; | |
while (n != null) { | |
if (n.value == value) { | |
find = n; | |
break; | |
} else if (n.value > value) { | |
n = n.left; | |
} else { | |
n = n.right; | |
} | |
} | |
if (find == null) { | |
throw new NoSuchElementException("No node with that value in this tree"); | |
} | |
// If we have a right child, get the next element via | |
// an in order traversal | |
if (find.right != null) { | |
BinaryTreeNode cur = find.right; | |
while (cur.left != null) { | |
cur = cur.left; | |
} | |
return cur; | |
} | |
BinaryTreeNode successor = null; | |
n = root; | |
while (n != find) { | |
if (n.value > value) { | |
successor = n; | |
n = n.left; | |
} else { | |
n = n.right; | |
} | |
} | |
return successor; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment