Find inorder successor in a binary search tree
Algorithm to find successor in a binary search tree.
Here we want to find successor of given binary tree.
Algorithm
package com.omt.learn.algo; import com.omt.learn.algo.util.tree.TreeNode; public class TreeSuccessor { public static void main(String[] args) { TreeNode find = new TreeNode(new TreeNode("11"), null, "12"); TreeNode root = generateTree(find); System.out.println(successor(find).nodeName); } public static TreeNode successor(TreeNode n) { if (n.rightNode != null) { return leftMostNode(n.rightNode); } return parentSuccessor(n); } public static TreeNode parentSuccessor(TreeNode n) { TreeNode p = n.parentNode; while (p != null) { if (p.leftNode == n) { return p; } n = p; p = p.parentNode; } return p; } public static TreeNode leftMostNode(TreeNode n) { if (n == null) { return null; } while (n.leftNode != null) { n = n.leftNode; } return n; } public static TreeNode generateTree(TreeNode findingNode) { TreeNode n = new TreeNode(new TreeNode(new TreeNode(new TreeNode("6"), null, "8"), findingNode, "10"), new TreeNode(new TreeNode(new TreeNode("16"), null, "17"), new TreeNode(null, new TreeNode("27"), "25"), "20"), "15"); return n; } }
TreeNode.java
package com.omt.learn.algo.util.tree; public class TreeNode { public String nodeName = ""; public boolean isVisited = false; public int value = 0; public TreeNode leftNode = null; public TreeNode rightNode = null; public TreeNode parentNode = null; public TreeNode() { // TODO Auto-generated constructor stub } public TreeNode(String name) { nodeName = name; } public TreeNode(TreeNode left, TreeNode right, String name) { leftNode = left; rightNode = right; nodeName = name; setParent(); } private void setParent() { if (leftNode != null) { leftNode.parentNode = this; } if (rightNode != null) { rightNode.parentNode = this; } } }
Check here more about what is successor.