When an element is added to a binary search tree, a new node is added as a child of an existing node. Before the addition, was this existing node always, sometimes, or never a leaf? Explain. In the...

When an element is added to a binary search tree, a new node is added as a child of an existing node. Before the addition, was this existing node always, sometimes, or never a leaf? Explain.

In the worst case, searching a binary search tree takes linear time. Can this happen when performing a binary search (Section 8.2) on a sorted array? Explain.