item. The predecessorfunction returns the largest item in the tree that is smaller than the given item. Both functions will return -1 if not found. Note that the predecessor or successor may exist even if the given item is not present in the tree
(Python)- Implement functions successor and predecessor. These functions will take two arguments: the root of a tree and an integer. The successor function returns the smallest item in the tree that is greater than the given item. The predecessorfunction returns the largest item in the tree that is smaller than the given item. Both functions will return -1 if not found. Note that the predecessor or successor may exist even if the given item is not present in the tree.
Use this template:
# Node definition provided, please don't modify it.
class TreeNode:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
# TODO: Please implement the following functions that return an integer
# Return the largest value in the tree that is smaller than given value. Return -1
if not found.
def predecessor(root, value):
pass
# Return the smallest value in the tree that is bigger than given value. Return -1
if not found.
def successor(root, value):
pass
if __name__ == "__main__":
# TODO: (Optional) your test code here.
my_root = TreeNode(3)
my_root.left = TreeNode(1)
my_root.right = TreeNode(5)
my_root.right.left = TreeNode(4)
print(successor(my_root, 2)) # expected 3
print(predecessor(my_root, 2)) # expected 1
print(successor(my_root, 3)) # expected 4
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
