Optimal Binary Search Trees

Learn about the optimal binary search trees problem and its solution using backtracking.

Introduction to optimal binary search trees

Our final example combines recursive backtracking with the divide-and-conquer strategy. Recall that the running time for a successful search in a binary search tree is proportional to the number of ancestors of the target node. As a result, the worst-case search time is proportional to the depth of the tree. Thus, to minimize the worst-case search time, the height of the tree should be as small as possible; by this metric, the ideal tree is perfectly balanced.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy