2 votes 2 votes options are - 1) <=n^2 always 2) >=nlogn always 3) n^2 4)O(n) for some special trees DS data-structures binary-tree + – Nachiket Karambelkar asked Jun 21, 2016 recategorized Jul 6, 2022 by Lakshman Bhaiya Nachiket Karambelkar 1.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes If binary tree external nodes=n, then internal nodes =(n-1) Path length from root to leaf will be O(log n) As there are n external nodes, so n such path exists So, total length of external path = n log n Ans 2) srestha answered Jun 21, 2016 srestha comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Tesla! commented Oct 25, 2017 reply Follow Share @sreshta if I have skewed binary tree then for n external node I won't have n-1 internal node 0 votes 0 votes srestha commented Oct 25, 2017 reply Follow Share @ Tesla! skewed tree cannot be ans. As there are n external nodes, there must be n-1 internal nodes and skewed tree has only one external node 0 votes 0 votes Tesla! commented Oct 25, 2017 reply Follow Share My bad yes skewed not possible, what about option A 0 votes 0 votes Please log in or register to add a comment.