Analysis of Bst height Let xn be the random variable denoting the height of a randomly built binary search tree on n nodes and let y 2An be its exponential height If the root of the tree has rank k then Xn=1+max(xk-1, Xn-kj since each of the left and right subtrees of the root are randomly built Hence we have Yn=2 max(Yk-1, In-k c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.16© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.16 Analysis of BST height Let Xn be the random variable denoting the height of a randomly built binary search tree on n nodes, and let Yn = 2Xn be its exponential height. If the root of the tree has rank k, then Xn = 1 + max{Xk–1, Xn–k} , since each of the left and right subtrees of the root are randomly built. Hence, we have Yn = 2· max{Yk–1, Yn–k}