Search code examples
binary-treebinary-search-treedepth

Binary Tree MIN and MAX Depth

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?

Solution

  • 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.