WRITE IN C++ Enter integers through the keyboard. While entering the numbers, create a binary search tree. For a NULL node enter -1. For the created binary tree write its preorder, inorder, postorder and level order traversals. Then, ask the user to insert a value of a node in the tree. Write a function to find the predecessor of the given node (its value and address).

If the node is not found, the function should return NULL. If the found node is the root, the function should return NULL, as well. If the first value that is entered is equal to -1, then don't print the tree, its traversals or the predecessor of the given node, but instead only print a message that the tree is empty.

Example output:

 

Enter the value for the root (-1 for empty tree): 5 Enter the next element to enter in the binary search tree