0 votes 0 votes DS made-easy-test-series data-structures binary-tree time-complexity + – varun singh asked Feb 6, 2017 • recategorized Mar 5, 2019 by adeebafatima1 varun singh 602 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 5 nodes have max levels=5 n nodes have max level=n For binary tree max height = number of levels -1 so O(n) is correct. Shubham Sharma 2 answered Feb 4, 2017 Shubham Sharma 2 comment Share Follow See all 2 Comments See all 2 2 Comments reply vaishali jhalani commented Feb 4, 2017 reply Follow Share n are no of leaf nodes..not the total no of nodes 0 votes 0 votes Shubham Sharma 2 commented Feb 4, 2017 reply Follow Share then take i as total number of nodes. assume i=N so O(N) is correct. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes The height of the binary tree in the worst case is O(N). We can calculate the the function g(x) in constant time C , therefore total cost is O(cN) or O(N) in the worst case. This is O(logN) in the best case. Durgesh Singh answered Jun 15, 2017 Durgesh Singh comment Share Follow See all 2 Comments See all 2 2 Comments reply Saikat commented Jul 3, 2017 reply Follow Share They are saying that g(x) is applied for each node in the binary tree. So shouldn't it be 1+2+3 +...+N = O(N2) where N is total no of nodes in the binary tree? Also I think the question is wrong. They gave there are n leaf nodes. How do we get total no of nodes in the tree? In worst case n will be 1 and height can be anything. So how do we compute TC for this program? 0 votes 0 votes vamp_vaibhav commented Nov 30, 2017 reply Follow Share Saikat.. I think it won't be o(n2) because the calculation of differences between left subtree and right subtree takes constant time only..You are calculating the sum of differences which is not desirable if it ask about the complexity .. And therefore in worst case it would be of O(n).. 0 votes 0 votes Please log in or register to add a comment.