recategorized by
897 views
1 votes
1 votes

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?

recategorized by

1 Answer

3 votes
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.

Related questions

2 votes
2 votes
1 answer
2
eyeamgj asked Nov 19, 2018
711 views
1 votes
1 votes
2 answers
3
CHïntän ÞäTël asked Dec 10, 2018
977 views
four vertices {A,B,C,D} is given which has only vertex D as a leaf total number of binary tree are possible when every binary tree has four node!