is O(n) big or O(nlogn)?? how is it better??
On Sat, Oct 3, 2009 at 12:30 PM, harit agarwal wrote:
> try this
> do the DFS analogous traversal on the tree.means
> 1.set level=1,push root
> 2.pop root
> 3.push both children on stack and set increment level .
> 4.now pop top and recursive
degcba?
for each level, use a deque to store nodes, if you want to output the
tree from left to right, traverse the deque from begin to end;
otherwise from end to begin
On 10月7日, 下午4时23分, umesh kewat wrote:
> hi,
> add some more constrain on above problem
> here desired output isg e d c b
hi,
add some more constrain on above problem
here desired output isg e d c b a for given tree what will be approach
if desired output level wise like
degbca
Traversing the tree from left to right in place of right to left in level
wise bottom to top.. [:)]
2009/10/7 hopper
>
> harit'
harit's method is the typical one about width first search, it can
solve the problem.
On 10月7日, 上午3时59分, Manisha wrote:
> Thanks a Ton everybody!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" gr
Thanks a Ton everybody!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeek
try this
do the DFS analogous traversal on the tree.means
1.set level=1,push root
2.pop root
3.push both children on stack and set increment level .
4.now pop top and recursively do the same thing
every time u pop an element enque it in a max priority queue according to
level
when traver
nice
but what if its a generic tree .. I mean each node can have any no of
children 2,3,4 ,5
How do you traverse it from bottom to top then ??
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
On 2 říj, 16:07, Manisha wrote:
> Traversing a binary tree from bottom to top
>
> The only way I could think of is:
> Traverse the binary tree from top to bottom, level by level with the
> help of queue.
> For a tree like:
> a
> b c
> d
We could do in O(log n) space and O(nlog n) time complexity. Traverse once
to find the maximum depth d ~= log n keeping track of the trail upto root
(just as with any recursive traversal). Then traverse d times but visit
nodes at depth d, d-1 ... 1 in each traversal.
We could optimize the implement