Is Binary Search Related to Binary Search Tree? I was reading binary search and suddenly realized that it would be very difficult for a binary search tree to find the middle value and then split in two. Are these related at all?
A balanced binary search tree describes the working of the binary search algorithm on a sorted list. The root should contain the middle element, the left subtree the left half, the right subtree the right half, and so on recursively. The tree also has to be balanced, that is, to reflect the fact that we chose the middle element as the root. In this sense, a binary search tree is a generalization of binary search on a sorted list.