Finding the predecessor in the binary tree.

Problem

Given the root pointer of the binary tree and the pointer to the target node, find the predecessor of the target node.

For example, in Figure 1. the predecessor of  5 is 4.

In finding the predecessor, we need to consider two cases.

Case 1: the target node has a left child

Let's take the example of "5" in the tree, it has the left child, "3". In this case, the predecessor is the right-most node of the node, "3". if "3" has the right children. This is a simple case. In this example "4" is the predecessor.

Case 2: the target node does not have a left child.

However, if the target node is "6", things become a little tricky. In this case, its parent "5" is the predecessor. More specifically, the parent node of the target node if the target node is the parent's right child.
This means we need to keep track of the parent while we are searching.

Given the binary tree lacking the parent pointer, we need to have an extra pointer to store the lastly encountered parent. This will require a preliminary search to find the target node's parent.

To summarize, here are the steps we need to implement.

1) Find the target node from the root of the tree. Keep track of the parent node during the search.

2) Check if the target node suit Case 1 or Case 2 and find the predecessor.

Here is the complete code running in O(log N), where N is the number of nodes in the tree.

UPDATE(2022-06-12): Reviewed the problem again and found that I misunderstood the problem. The explanation I had was for finding the predecessor, not the successor.  Fixed the wording and the title.

I will add another example to find the successor of the target node in a separate post.

Also, prior solutions were wrong in that both solutions fails to find the predecessor in the parent tree.

The following is the complete solution in python.

	#input
	class Node:
	def __init__(self, value):
	self.value = value
	self.left = None
	self.right = None
	def __str__(self):
	return str(self.value)
	# solution
	def search_binary(parent, cur, target, path):
	# add the parent of the current node.
	path[cur.value] = parent
	if cur is None:
	# failed to find the target.
	return None
	if cur.value == target:
	return cur
	if cur.value < target:
	return search_binary(cur, cur.right, target, path)
	else:
	return search_binary(cur, cur.left, target, path)
	def find_right_most_child(current):
	# check if target has the the left child.
	if current.right is None:
	return current
	return find_right_most_child(current.right)
	def find_parent_predecessor(current, parents):
	if current.value in parents and parents[current.value] != None:
	parent = parents[current.value]
	#check if current node is the right child of the parent
	if parent.right == current:
	return parent
	else:
	return find_parent_predecessor(parent, parents)
	else:
	# no more rightful parent found. node might be the root.
	return None
	def find_predecessor(root, target):
	path = {}
	# first find the target node O(log N)
	found = search_binary(None, root, target, path)
	if target is None:
	return None
	# check if target has the the left child. O(log N)
	if found.left is not None:
	return find_right_most_child(found.left)
	# search the parent for predecessor. O(log N)
	return find_parent_predecessor(found, path)
	# test
	c9 = Node(9)
	c5 = Node(5)
	c10 = Node(10)
	c9.left = c5
	c9.right = c10
	c3 = Node(3)
	c6 = Node(6)
	c5.left = c3
	c5.right = c6
	c11 = Node(11)
	c10.right = c11
	c2 = Node(2)
	c4 = Node(4)
	c3.left = c2
	c3.right = c4
	c7 = Node(7)
	c6.right = c7
	c12 = Node(12)
	c11.right = c12
	root = c9
	target = 5
	found = find_predecessor(root, target)
	print("predecessor for {} is {}".format(target, found))
	target = 2
	found = find_predecessor(root, target)
	print("predecessor for {} is {}".format(target, found))
	target = 6
	found = find_predecessor(root, target)
	print("predecessor for {} is {}".format(target, found))

view raw find_predecessor.py hosted with ❤ by GitHub