Find Next Node of BST

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

public TreeNode findNext(TreeNode node) {
	if(node == null) return null;
	if(node.parent==null || node.right != null) {
		// find left most child in right sub tree
		TreeNode next = node.right;
		while(next.left != null) next = next.left;
		return next;
	} else {
		// go up until we are on the left side of parent node
		TreeNode p = node.parent;
		while(p != null && p.left != node) {
			node = p;
			p = p.parent;
		}
		return p;
	}
}

  

如果没有父节点的话，可以这么做：

public TreeNode findNext(TreeNode root, TreeNode node) {
	if(root == null || node == null) return null;
	if(node.right != null) {
		TreeNode n = node.right;
		while(n.left != null) {
			n = n.left;
		}
		return n;
	}
	TreeNode n = null;
	while(root != null) {
		if(root.val > node.val) {
			n = root;
			root = root.left;
		} else if(root.val < node.val) {
			root = root.right;
		} else {
			break;
		}
	}
	return n;
}

 

Reference:

http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/