class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def levelOrderSuccessor(root, key):
if root == None:
return None
elif root == key:
if root.left:
return root.left
elif root.right:
return root.right
else:
return None
q = []
q.append(root)
while len(q) != 0:
nd = q.pop(0)
if nd.left != None:
q.append(nd.left)
if nd.right != None:
q.append(nd.right)
if nd == key:
break
return q[0]
if __name__ == "__main__":
root = Node(20)
root.left = Node(10)
root.left.left = Node(4)
root.left.right = Node(18)
root.right = Node(26)
root.right.left = Node(24)
root.right.right = Node(27)
root.left.right.left = Node(14)
root.left.right.left.left = Node(13)
root.left.right.left.right = Node(15)
root.left.right.right = Node(19)
key = root.right.left # node 24
res = levelOrderSuccessor(root, key)
if res:
print("LevelOrder successor of " +
str(key.value) + " is " +
str(res.value))
else:
print("LevelOrder successor of " +
str(key.value) + " is NULL")