MadeEasy Subject Test: Programming & DS - Binary Tree

Question

Answer 1

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.

Comments

n are no of leaf nodes..not the total no of nodes

---

then take i as total number of nodes.

assume i=N

so O(N) is correct.

Answer 2

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.

Comments

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(N²) 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?

---

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)..