Consider a binary search tree with n nodes and height h where: Every internal no

Question

Consider a binary search tree with n nodes and height h where: Every internal node in the tree has exactly two children. (No nodes with only one child.) For each internal tree node x, the heights of the subtrees rooted at x.left and x.right differ by at most 1. Prove that if the subtree rooted at x has height h', then the heights of the subtrees rooted at x.left and x.right are at least h' - 2. Using your answer to part a.), prove that if the binary search tree has height h, then the length of the shortest path from the root to any leaf is at least [h/2]. Using your answer to part b.), prove that if the binary search tree has height h, then the tree has at least 2[h/]+1 -1 nodes. Using your answer to part c.), prove that if the binary search tree has n nodes, then the tree has height at most 2 lg(n +1).

Explanation / Answer

As mentioned in question that binary search tree with n nodes and h height where every node has exctly two children so that it cab be either AVL tree or Red black tree. Now AVL tree is very well balanced tree and the that is not mentioned so we can consider it as red black tree.

b) if the binary tree has hieght h then the shortest path for the root is h/2

   we know that the time complexity of BST is log2(n) that means every time while searching element or unserting element we rule out half the space of the tree. since BSt is sorted tree it means either the element which is beaing searched either in left or right side of the root node so either we rule out left tree or right tree on root. now the same will be performed at evevry node until the tree hight does equal to 1.
   so at every case element will get seached at h/2 until we reach at corrct node of tree hight 1 ( or element not found case )

   so we can say inn every iteration we rule out the entire half of tree so we can say that the shortest path for the root node is h/2
  

D)   We know that time complexity of binary search tree for search, insert and delete operation is o(log n) then
  
   The total number of nodes in the BST is equal to the sum of the nodes on all the levels: nodes n.
  
       1 + 2 power(1) + 2power(2) + 2power(3) + ... + 2 power(h) = n
      
       2 power(h+1) - 1 = n
      
       2 power ( h + 1) = n + 1

   taking both side log

      
       log2 ( h + 1) = log2 ( n + 1)
      

       (h + 1) log2 (power 2) = log2(n + 1)
      

       h + 1 = log2 ( n + 1 )

       h = log2 ( n + 1 ) - 1

   We can say the above term is

       h = log2 ( n) + constants

   constants can be ignored here so finally

       h = log2(n)

C ) let suppose we have n node in tree so we can say and every node has their left or right node or we cna say balacnced tree.

   so we can write following series and represent the tree

   1 + 2 power(1) + 2power(2) + 2power(3) + ... + 2 power(h) = n

   2 - 1 + 2 power(1) + 2power(2) + 2power(3) + ... + 2 power(h) = n

   2 - 2 power ( h ) = n

   2 power ( h - 1) = n

   2 power (( h - 1) /2) = n

   2 [ h / 2] + 1 - 1 = n

  

  
  

  

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.