Binary Tree MIN and MAX Depth

Question

I am having trouble with these questions:

A binary tree with N nodes is at least how deep? How deep is it at most?

Would the maximum depth just be N?

Answer 1

There are two extremes that you need to consider.

1. Every node has just a left(or right) child, but not right child. In which case your binary search tree is merely a linkedlist in practice.
2. Every level in your tree is full, maybe except the last level. This type of trees are called complete.
3. Third type of tree that I know may not be relevant to your question. But it is called full tree and every node is either a leaf or has n number of childs for an n-ary tree.

So to answer your question. Max depth is N. And at least it has log(N) levels, when it is a complete tree.