What Is The Expected Depth Of A Node In A Randomized Binary Search Tree?

› Category: Questions › What is the expected depth of a node in a randomized binary search tree?

Editor Staff asked 5 months ago

What is the expected depth of a node in a randomized binary search tree?

(a) log n

(b) n!

(c) n^2

(d) 2 log n + O(1)

Asked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms I

This question was posed to me in quiz.

Question Tags: Interview-Questions-Answers

1 Answers

0 Vote Up Vote Down

Editor">

Editor Staff answered 5 months ago

The correct choice is (d) 2 log n + O(1)

For explanation: The expected value of depth of a node that is for a node a, the expected value of length of path from root to node a is found to be at most 2 log n + O(1).

Related Posts

Most commonly asked OpenAI interview questions and answers

Common AI interview questions and answers:

How do you uninstall gulp?