MERGING TREES
Page 1 of 1 • Share •
MERGING TREES
Given two balanced binary trees,
how to merge them in minimum time so that final tree is also balanced???
how to merge them in minimum time so that final tree is also balanced???
prani- Posts: 15
Join date: 2008-08-12
@tiwari ji
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.
or
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)
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.
or
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)

shivang- Posts: 22
Join date: 2008-08-11
Age: 20
Location: Tondon 174
Permissions of this forum:
You cannot reply to topics in this forum





