Binary Search Tree

• A BST can only store elements if there exists some way of comparing them (e.g. strings, characters, numbers, etc.): there must be some inherent order between elements.
• functions: find, size, clear, insert, empty, successor, and the iterator
• successor(): finds the "successor"—the next largest node—of a given node in the BST.
  1. The given node has right child: visit right subtree
  2. The given node doesn't have right child: Starting at u, we can traverse up the tree. The moment we encounter a node that is the left child of its parent, the parent must be u's successor. If no such node exists, then u has no successor.
• A balanced binary tree is one where many (or most) internal nodes have exactly two children. A perfectly balanced binary tree is one where all internal nodes have exactly two children.
• A perfectly balanced binary tree with n elements has a height of log₂(n+1)-1
• Question: What is the worst-case time complexity of the find operation of a balanced Binary Search Tree with n elements?

Ans: O(logn)

REFERENCE: Stepik 3.3