Go down


Post  prani on Wed Aug 13, 2008 9:24 am

Given two balanced binary trees,
how to merge them in minimum time so that final tree is also balanced???


Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

MERGING TREES Empty @tiwari ji

Post  shivang on Mon Aug 18, 2008 12:34 pm

Do let me know if i am doing this correctly....
Step 1: Convert one of the trees into a linear list. this can be done in the following two ways
i)As it is given that the tree is perfectly balanced we can convert one tree into a linear list using the inorder traversal in O(n) time. But ya if the tree is not balanced this procedure will have to be altered and time complexity will increase.


ii)u can convert a tree into list by using the rotations that we studied in Red Black trees in same O(n) time complexity no matter if the tree is balanced or not/

Step 2: Add the list elements into the other tree by simple insert procedure. for one element to be inserted time will be O(lgn)
so the total time complexity will be O(nlgn)

Posts : 22
Join date : 2008-08-11
Age : 30
Location : Tondon 174

View user profile

Back to top Go down

Back to top

Permissions in this forum:
You cannot reply to topics in this forum