The average depth of a binary search tree is
The average case depth of a node in a BST is O(lg n)
A binary search tree is a binary tree with the further property that, for every node,
the value of the element in the left child is less than the value of the element at the node, and
the value of the element in the right child is greater than the value of the element at the node
The average depth over all nodes in a binary search tree is O(lg n)
X->YZ , Y->XZ , ...