Uhhhh, well, there is an 2^(1+lg(D))-1 time algorithm that uses constant memory for a tree of size D. So, that's O(D).
Just do df-traversal for all levels of the tree outputting only the nodes at current level. On Jan 31, 2:18 am, dor <[EMAIL PROTECTED]> wrote: > O(n) extra memory will suffice, and you already use O(n) memory to > store the tree, so I'm not sure what you mean by memory intensive. > It's certainly not the case that you will need a lot of additional > memory (otherwise, you could not store the tree in the first place). > > An inorder traversal (which does not solve the problem as you noted) > would require just as much additional memory -- and so does every > other solution I could think of. > > On Jan 30, 11:26 pm, DanielJohnson <[EMAIL PROTECTED]> wrote: > > > I was trying to solve this problem where we have a binary tree given > > and we have to print the values of the tree level by level i.e. root > > node then its left child, right child, then left child's both left and > > right, then right child's both left and right. > > > Since for very large tree using BFS can be memory intensive, so our > > restriction is not to use any queue data structure to perform BFS. > > > I have thought of using inorder traversal with modified algorithm but > > I just figured that out that it fails in certain cases. > > > Can anybody suggest an algorithm for this problem ? --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
