Pergunta de entrevista da empresa Amazon

Code to find median in BST

Respostas da entrevista

Sigiloso

20 de jan. de 2011

Where n = number of elements in the BST, use an in-order Depth first search to traverse the tree and return element n/2 + 1. (The +1 is needed, assuming that n is an odd number and there is a true single median value.)

1

Sigiloso

16 de nov. de 2010

Step 1) Do a Breadth first search/dump to count the number of elements. Step 2) Count half of that in your second breadth first dump and return the element.