+1 vote
230 views

A program takes input of a binary tree with N nodes and computes a function f(x)=max height of left subtree-max height of right subtree

what is the time complexity?

edited | 230 views
0
worst case O(N)

best case O(1)

??
0
why N ,not logn??

btw N is answer ,you correct
+1
it is a binary tree.

not an AVL tree, so that u have to maintain height.

So, It could be skew tree to, i.e. O(N)

Binary tree are not balanced, so in worst case, height can go up to N , so to find the

maximum height it will take O(N)  complexity.

Balanced tree means for each and every node in the tree the absolute difference of

maximum height of left  and right subtree should be less then equals to 1.

For each and every node ( u )   of a tree if  :

| maximum_height(left subtree of u) -  maximum_height(right subtree of u | <= 1

then it is said to be balanced.  Their difference can take value : { -1 , 0 , 1 }

For example : AVL tree ,  balanced binary search tree. ( height : log(N) )

If in any problem the tree they specified is binary search tree, then that tree is

considered as unbalanced unless and until they specify the keyword balanced.
by Active (3k points)
0
IN a madeeasy question N is the number of leaf nodes..then what will be the complexity?

My ans is nlogn
0

Answer will be always total number of nodes, So if  N number of leaf nodes are available,  It means

Maximum number of nods in the tree will be (2 * N - 1 )  which is again equivalent to N [ Linear ]

Hence again complexity will be O(N) . Because for each node , we have to calculate max left subtree height as well as max right subtree height ,  which we can calculate recursively , in bottom up manner.

So atleast we have to traverse the whole tree during recursion.

Complexity : 0(N).

1
2