Homework SourseProve that in a binary tree with n elements the high of the
Prove that in a binary tree with n elements, the high of the tree is greater than or equal to [log_2 (n)]. Prove that in a complete binary tree with n elements, the height of the tree is exactly [log_2 (n)].
![Prove that in a binary tree with n elements, the high of the tree is greater than or equal to [log_2 (n)]. Prove that in a complete binary tree with n elements](/WebImages/47/prove-that-in-a-binary-tree-with-n-elements-the-high-of-the-1148729-1761618080-0.webp "Prove that in a binary tree with n elements, the high of the tree is greater than or equal to [log_2 (n)]. Prove that in a complete binary tree with n elements")
Solution
let N be the number of nodes.
let H be the height of the binary tree.
For a complete binary tree
with H height N would lie between:
Thus, solving this inequality; we get :
now at last,
where lg is log base2
Binary Tree (not necessarily complete):
| let N be the number of nodes. For a complete binary tree with H height N would lie between: 2^H <= N <= (2^(H+1) - 1) Thus, solving this inequality; we get : H <= lg(N) and H >= (lg(N+1) - 1) now at last, H = floor( lg(N) ) = ceil( (lg(N+1) - 1) ) //as H is integer where lg is log base2 Binary Tree (not necessarily complete): Max height = N; Min Height = floor( lg(N) ) = ceil( (lg(N+1) - 1) ) |
