# 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