instagram

Find inorder successor in a binary search tree

by omt

Algorithm to find successor in a binary search tree.

Here we want to find successor of given binary tree.

BinaryTreeForSuccessor

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.

Share