1 votes 1 votes The minimum number of node in an AVL Tree of height $10$ is ____________ DS data-structures avl-tree + – Lakshman Bhaiya asked Nov 6, 2018 Lakshman Bhaiya 692 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply adarsh_1997 commented Nov 6, 2018 reply Follow Share n(h)=n(h-1)+1+n(h-2) =1 h=0 =2 h=1 use this u will get the answer 1 votes 1 votes Naveen Kumar 3 commented Nov 6, 2018 reply Follow Share assuming height 0 having 1 node & using h(n)=h(n-1)+h(n-2)+1 recursively h(10)=232. 1 votes 1 votes Lakshman Bhaiya commented Nov 6, 2018 reply Follow Share thanks 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes AVL Tree: AVL tree is the self-balancing Binary Search Tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Height(LST)-Height(RST) =−1,0,1 Rebalancing is needed at any time if they differ by more than one. Using the recursive function N(h) = 1 + N(h-1) + N(h-2) we can find the minimum number of nodes in any given AVL tree of height h. We know that N(0) = 1 N(1) = 2 N(2) = 4 N(3) = 1 + N(2) + N(1) => 1 + 2 + 4 = 7 N(4) = 1 + N(3) + N (2) => 1 + 7 + 4 = 12 N(5) = 1 + N(4) + N(3) => 1 + 12 + 7 = 20 N(6) = 1 + N(5) + N(4) => 1 + 20 + 12 = 33 N(7) = 1 + N(6) + N(5) => 1 + 33 + 20 = 54 N(8) = 1 + N(7) + N(6) => 1 + 54 + 33 = 88 N(9) = 1 + N(8) + N(7) => 1 + 88 + 54 = 143 N(10) = 1 + N(9) + N(8) => 1 + 143 + 88 = 232 Dhillu Thambi answered Nov 6, 2018 • edited Nov 6, 2018 by Dhillu Thambi Dhillu Thambi comment Share Follow See all 2 Comments See all 2 2 Comments reply Lakshman Bhaiya commented Nov 6, 2018 reply Follow Share In AVL Tree Height(LST)-Height(RST) $= {-1,0,1}$ Otherwise Rebalancing is needed. 0 votes 0 votes Dhillu Thambi commented Nov 6, 2018 reply Follow Share Yep. Added this point to the answer :) 0 votes 0 votes Please log in or register to add a comment.