The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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?

in Algorithms by Boss (17.9k points)
edited by | 230 views
worst case O(N)

best case O(1)

why N ,not logn??

btw N is answer ,you correct
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)

1 Answer

+3 votes
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)
IN a madeeasy question N is the number of leaf nodes..then what will be the complexity?

My ans is nlogn

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

 vaishali jhalani

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,239 answers
85,992 users