Trees

• Binary search tree


  A tree data structure in which all the nodes in the left subtree have a value less than the root node, and all the nodes in the right subtree have a value greater than the root node
• Implementing binary search tree functions

  1. Read and understand the code

  2. Execute the code and learn how to use it

  3. Implement in-order traversal

  4. Implement post-order traversal

  5. Implement search function

  6. Implement sum function

  7. Calculate time complexity of each function

  8. Implement remove function

  9. Implement getRMin helper function
• The activities are not meant to be totally finished during the lab session
• The code starts with a BST already constructed, but the user can change it to start with an empty tree and insert their own nodes
• The traversals In-Order and Post-Order and the function remove() are already included in the menu, but they are not implemented yet
• The remove() function must take care of three different situations
• The getRMin() function gets the leftmost child of the right node