BST of minimal height

2
votes

I'm trying to solve the following problem: "Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a BST with minimal height."

The given answer takes the root node to be the middle of the array. While doing this makes sense to me intuitively, I'm trying to prove, rigorously, that it's always best to make the root node the middle of the array.

The justification given in the book is: "To create a tree of minimal height, we need to match the number of nodes in the left subtree to the number of nodes in the right subtree as much as possible. This means that we want the root node to be the middle of the array, since this would mean that half the elements would be less than the root and half would be greater."

I'd like to ask:

  1. Why would any tree of minimal height be one where the number of nodes in the left subtree be as equal as possible to the number of nodes in the right subtree? (Or, do you have any other way to prove that it's best to make the root node the middle of the array?)

  2. Is a tree with minimal height the same as a tree that's balanced? From a previous question on SO, that's the impression I got, (Visualizing a balanced tree) but I'm confused because the book specifically states "BST with minimal height" and never "balanced BST".

Thanks.

Source: Cracking the Coding Interview

2
arrayssortingbinary-search-treetree-balancing

2 Answers

0
votes

  1. The way I like to think about it, if you balance a tree using tree rotations (zig-zig and zig-zag rotations) you will eventually reach a state in which the left and right subtree differ by at most height of one. It is not always the case that a balanced tree must have the same number of children on the right and the left; however, if you have that invariant(same # of children on each side), you can reach a tree that is balanced using tree rotations)

  2. Balance is defined arbitrarily. AVL trees define it in such as way that no subtree of the tree has a children whose heights differ by more than one. Other trees define balance in different ways, so they are not the same distinction. They are inherently related yet not exactly the same. That being said, a tree of minimal height will always be balanced under any definition since balancing exists to maintain a O(log(n)) lookup time of the BST.

If I missed anything or said anything wrong, feel free to edit/correct me. Hope this helps

0
votes

Why would any tree of minimal height be one where the number of nodes in the left subtree be as equal as possible to the number of nodes in the right subtree?

There can be a scenario where in minimal height tree which are ofcourse balanced can have different number of node count on left and right hand side. BST worst case traversal is O(n) in case if it is sorted and in minimal height trees the complexity for worst case is O(log n).

    *
   / \
  *   *
 /
*

Here you can clearly see that left node count and right nodes are not equal though it is a minimal height tree.

Is a tree with minimal height the same as a tree that's balanced? From a previous question on SO, that's the impression I got, (Visualizing a balanced tree) but I'm confused because the book specifically states "BST with minimal height" and never "balanced BST".

Minimal height tree is balanced one, for more details you can take a look on AVL trees which are also known as height-balanced trees. While making BST a height balanced tree you have to perform rotations (LR, RR, LL, RL).