human
Inorder predecessor and successor for a given key in BST | Iterative Approach | Function that finds predecessor and successor of key in BST ..
Search for given key in BST ..
If root is given key ..
the minimum value in right subtree is predecessor ..
the maximum value in left subtree is successor ..
If key is greater than root , then key lies in right subtree . Root could be predecessor if left subtree of key is null ..
If key is smaller than root , then key lies in left subtree . Root could be successor if right subtree of key is null ..
A utility function to create a new BST node.
A utility function to insert a new node with given key in BST.
Driver Code.
Key to be searched in BST.
Let us create following BST 50 / \ / \ 30 70 / \ / \ / \ / \ 20 40 60 80"
How can the above be solved in Python?
 ... Write me a code to inorder predecessor and successor for a given key in BST and the other steps required?
assistant
#Here is code to inorder predecessor and successor for a given key in BST and the other steps required.
 def findPreSuc ( root , pre , suc , key ) :
	if root == None :
		return
	while root != None :
		if root . key == key :
			if root . right :
				suc [ 0 ] = root . right
				while suc [ 0 ] . left :
					suc [ 0 ] = suc [ 0 ] . left
			if root . left :
				pre [ 0 ] = root . left
				while pre [ 0 ] . right :
					pre [ 0 ] = pre [ 0 ] . right
			return
		elif root . key < key :
			pre [ 0 ] = root
			root = root . right
		else :
			suc [ 0 ] = root
			root = root . left
class newNode :
	def __init__ ( self , data ) :
		self . key = data
		self . left = None
		self . right = None
def insert ( node , key ) :
	if node == None :
		return newNode ( key )
	if key < node . key :
		node . left = insert ( node . left , key )
	else :
		node . right = insert ( node . right , key )
	return node
if __name__ == ' _ _ main _ _ ' :
	key = 65
	root = None
	root = insert ( root , 50 )
	insert ( root , 30 )
	insert ( root , 20 )
	insert ( root , 40 )
	insert ( root , 70 )
	insert ( root , 60 )
	insert ( root , 80 )
	pre , suc = [ None ] , [ None ]
	findPreSuc ( root , pre , suc , key )
	if pre [ 0 ] != None :
		print ( " Predecessor ▁ is " , pre [ 0 ] . key )
	else :
		print ( " - 1" )
	if suc [ 0 ] != None :
		print ( " Successor ▁ is " , suc [ 0 ] . key )
	else :
		print ( " - 1" )