Find the in-order successor of a node in a BST

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

My initial thoughts:
There are three cases:

  1. The node has a right children. Then the ‘next’ node is the left-most node in the right subtree.
  2. The node has no right children but it has a parent.
    • The node is its parent’s left child (i.e., the node is less than its parent): then its parent is its ‘next’ node.
    • The node is its parent’s right child (i.e., the node is greater than its parent): then we climb one level up and examine the parent’s parent.

My initial codes:

	public static BinaryTreeNode2<Integer> findNext(
			BinaryTreeNode2<Integer> root, BinaryTreeNode2<Integer> node) {
		if (node.getRight() != null) {
			// left-most in the right subtree
			BinaryTreeNode2<Integer> rightChild = node.getRight();
			BinaryTreeNode2<Integer> ptr = rightChild;
			while (ptr.getLeft() != null) {
				ptr = ptr.getLeft();
			}
			return ptr;
		}
		if (node.getParent() != null) {
			BinaryTreeNode2<Integer> parent = node.getParent();
			if (parent.getLeft() == node) { // parent is on the right
				return parent;
			} else if (parent.getRight() == node) { // parent is on the left
				BinaryTreeNode2<Integer> ptr = parent;
				while (ptr.getParent() != null) {
					parent = ptr.getParent();
					if (parent.getLeft() == ptr)
						break;
					ptr = parent;
				}
				return parent;
			}
		}
		return null;
	}

Comments after running:
Can’t handle the case where the query node is the right-most node (i.e., the largest number in the sorted array that build this BST, whose ‘next’ node is supposed to be null). The output is the root node. The highlighted lines 18 and 24 make this happen. Because if we climb up all the way from the right-most node, we will end up at the root node. Since the root’s parent is null, the program will return the root. But it’s supposed to return null. Correction (to replace line 18 to 24):

				while (ptr.getParent() != null) {
					parent = ptr.getParent();
					if (parent.getLeft() == ptr)
						return parent;
					ptr = parent;
				}

Also, an edge case should be considered before anything else:

		if(node == null) return null;

Solution:

	public static BinaryTreeNode2 inorderSucc(BinaryTreeNode2 e) {
		if (e != null) {
			BinaryTreeNode2 p;
			// Found right children -> return 1st inorder node on right
			if (e.getParent() == null || e.getRight() != null) {
				p = leftMostChild(e.getRight());
			} else {
				// Go up until we’re on left instead of right (case 2b)
				while ((p = e.getParent()) != null) {
					if (p.getLeft() == e) {
						break;
					}
					e = p;
				}
			}
			return p;
		}
		return null;
	}

	public static BinaryTreeNode2 leftMostChild(BinaryTreeNode2 e) {
		if (e == null)
			return null;
		while (e.getLeft() != null)
			e = e.getLeft();
		return e;
	}

Comments: the solution combine my 2nd and 3rd case together.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: