GATE Overflow Test Series | Data Structures | Test 1 | Question: 21

Question

If the best time complexity (not the best case input but the best algorithm which will work for any input) for finding the shortest path between two keys $a$ and $b$ in a balanced binary search tree of $n$ nodes is denoted by $\Theta(n^a (\log n)^b),$ then $2^a\times 3^b =$_____

Answer 1

The shortest path between any two nodes in a binary search tree can be found in $O(h)$ where $h$ is the height of the binary tree. This can be done by finding the lowest common ancestor and then finding the distance of both the keys and adding them. For a balanced binary tree height will be $\Theta(\log n).$ So, we get $ a = 0, b = 1 \implies 2^a \times 3^b = 3.$

Comments

How is it O(h)? Consider a case where the leftmost leaf and rightmost leaves are the two nodes. How can we find the shortest path between them in O(h)?

---

$O(h)$ doesnt mean $\leq h.$ $\leq c .h,$ where $c$ is a constant is also $O(h).$

---

refer:

https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/