Picking the structure!!

Use of arrays, rather sorted arrays or a linked list is somewhat difficult because both have their pros and cons. 

Arrays excel when we have to perform a binary search while it’s faster to add and remove elements from linked lists. 

A tree is one structure where there is ONLY ONE path to reach to a node. This can be explained further as “Nodes cannot be in closed loop”. Also there is a hierarchical relationship of parent and child.

The average complexity varies from logarithmic to linear time.

Now coming further to a data structure BSTs aka Binary Search Trees. Points to be remembered here:-

1. Maximum two children.
2. Left child is smaller than parent.
3. Right one is greater than parent.

Traversals:-
 
In order Traversal

Ascending Sort; left subtree + root+ right subtree. So the above tree will look like:  4, 12, 16, 25, 28, 32

Pre order Traversal

Root + left subtree + right subtree recursively. Eg: 25, 12, 4, 16, 32, 28

Post Order Traversal (left, right, root)

Eg: 4, 16, 12, 28, 32, 25

Height of tree is given by formula 2(h-1)

Deletion in a tree:-
There lies 3 cases:-

1. When node to be deleted is a leaf node. 
2. The node has a single child. 
3. The node has two children. In this case find the predecessor or successor of that particular node, which is Greatest node in the Left subtree or Smallest node in the Right subtree. Replace the concerned node with any of the two.