Binary Search Tree

Insertion in a sorted array still takes O(n) because once you can search for an index by O(log(n)) but if you want to insert an element in that position, you will need to shift all the elements which will take O(n).
So we will need a data structure that can allow us to insert an element with the time complexity less than O(n).

Here for each node there are 3 pointers:

1. Parent Node
2. Left Child
3. Right Child

For all nodes X, if Y is in the left subtree then key(y) <= key(x). If Y is in the right subtree then key(y) >= key(x).

If h is the height of the tree then insertion takes O(h)

Inorder Successor:

Case 1: If a node has a right subtree, then go deep to the leftmost node in the right subtree or Find the minimum in the right subtree
Case 2: If a node has no right subtree, go to the nearest ancestor for which the given node would be in the left subtree.