Binary Search Trees

Write a recursive function BSTsmallcount that, given a BST and a value key, returns the number of nodes having values less than key. Your...

What is the average time complexity for inserting an element into a binary search tree?