wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: Binary Tree Print
        
(Message started by: Jonathan the Red on Aug 1^st, 2002, 1:20pm)

Title: CS: Binary Tree Print
Post by Jonathan the Red on Aug 1^st, 2002, 1:20pm

Quote:

How would you print out the data in a binary tree, level by level, starting at the top?

Well, the below works...

Code:

struct Node
{
int m_nData;
Node* m_pLeft;
Node* m_pRight;
};

void PrintBinaryTree(Node* pNode)
{
int nLevel = 0;

if (pNode)
{
while (PrintTreeRecursive(pNode, 0, nLevel++))
;
}
}

bool PrintTreeRecursive(Node* pNode, int nCurrentLevel, int nDesiredLevel)
{
bool bRet = false;

if (nCurrentLevel == nDesiredLevel)
{
printf("%d ", pNode->m_nData);
bRet = true;
}
else
{
if (pNode->m_pLeft)
{
bRet = bRet || PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel);
}
if (pNode->m_pRight)
{
bRet = bRet || PrintTreeRecursive(pNode->m_pRight, nCurrentLevel+1, nDesiredLevel);
}
}

return bRet;
}

...but it takes O(n log n) to complete. Can it be done more efficiently?

Title: Re: CS: Binary Tree Print
Post by Jonathan the Red on Aug 1^st, 2002, 1:25pm

I'm a gimboid... change the lines that look like this:

Code:

bRet = bRet || PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel);

...to this. Damned short-circuiting...

Code:

bRet = PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel) || bRet;

Title: Re: CS: Binary Tree Print
Post by -D- on Aug 1^st, 2002, 1:30pm

To print out level by level I would use a breadth first search. Running time is O(|V|+|E|) which is some kind of linear.

You need a queue of pointers to nodes of the tree.

Basic algorithm

PrintTree()
{
enqueue( head )

while( p = dequeue() )
{
print_element_at( p );
enqueue( p.left );
enqueue( p.right );
}
}

Title: Re: CS: Binary Tree Print
Post by -D- on Aug 1^st, 2002, 1:37pm

I'm a dork. O(|V|+|E|) is for graphs, this is a tree, it should just be O(n). Although a binary tree can be considered a special form of graph.
-D-

Title: Re: CS: Binary Tree Print
Post by srowen on Aug 1^st, 2002, 5:19pm

Yeah, breadth-first traversal using the queue is the elegant way... faster than repeatedly depth-first-searching the tree, deeper each time.

If you substitute "push" for "enqueue" and "pop" for "dequeue" (i.e., use a stack instead of a queue) into this same basic algorithm you get depth-first search. First time I saw that I thought that was a great insight.

Title: Re: CS: Binary Tree Print
Post by -D- on Aug 1^st, 2002, 10:37pm

How would push/pop be able to replace enqueue/dequeue?

1
/ \
2 3
/ \ / \
4 56 7

push 1
pop 1
push 2
push 3
pop 3
push 6
push 7
pop 7 <-- error

I'm assuming i made a mistake in my thinking...
-D-

Title: Re: CS: Binary Tree Print
Post by -D- on Aug 1^st, 2002, 10:42pm

I'm a dork again... I thought you said it would do the same thing. You're right, it'll do a depth first search.

However if you're going to do a depth first search, you might as well just use recursion, it's just about as costly and you don't have to use a stack.

PrintTreeDepthFirst()
{
PrintNode( head );
}

PrintNode( node *p )
{
printElement( p );
PrintNode( p->left );
PrintNode( p->right );
}

... vs ...

PrintTreeDepthFirst()
{
push( head )
while( p = pop() )
{
printElement( p );
push( p->left );
push( p->right );
}
}

Neither way is any better I suppose.... I think I'd rather use recursion instead of set up a stack, and I -HATE- STL.
-D-

Title: Re: CS: Binary Tree Print
Post by S. Owen on Aug 7^th, 2002, 9:55am

on 08/01/02 at 22:42:20, -D- wrote:

However if you're going to do a depth first search, you might as well just use recursion, it's just about as costly and you don't have to use a stack.

And for our viewers - note that a recursive solution is using a stack too, but implicitly - the function call stack. Agreed that it's easier to not have to code that though.

Title: Re: CS: Binary Tree Print
Post by Nyarly on Aug 23^rd, 2002, 1:34pm

on 08/07/02 at 09:55:37, S. Owen wrote:

And for our viewers - note that a recursive solution is using a stack too, but implicitly - the function call stack. Agreed that it's easier to not have to code that though.

Easier to code, if you don't a stack implementation already. Harder to understand for any but a real hacker, and hardly more efficient. The call stack is almost always bigger than an a generic stack (what with return information and all), and you take the function call hit with every iteration. And besides, when you debug it, your call stack is going to grow and grow and... Of course, maybe that's better than you stack implementation indenting off the map...

OT - Why doesn't any debugger understand the idea of a linked list? Sometimes they do arrays nicely, (Codewarrior and gdb, but not MS's sludge) but I've yet to see a debugger not indent a linked list into oblivion (and Ritchee help you if you're looking a graph). >:(

Title: Re: CS: Binary Tree Print
Post by moonz on Jul 24^th, 2003, 12:43am

Another implementation without using the Node Levels instead.
;) prev mens "Left" and next means "Right" ..
int BinaryTree::findTreedepth(Node* node) {
if (!node)
return 0;
int x = findTreedepth(node->prev);
int y = findTreedepth(node->next);
return (x>y) ? 1+x:1+y;
}

void BinaryTree::printNodeLevelWise(Node *node,int printLevel, int depth) {
if (!node)
return;
depth++;
if (printLevel == depth)
printf("Node at Level %d is: %d\n",printLevel,node->val);
else
printNodeLevelWise(node->prev, printLevel, depth);
printNodeLevelWise(node->next, printLevel, depth);
}

void BinaryTree::printTreeLevelWise() {
int depth = findTreedepth(root);
if (!depth) return;
for (int i = 1 ; i <= depth ; i++) {
printNodeLevelWise(root,i,0);
}
}

Title: Re: CS: Binary Tree Print
Post by James Fingas on Jul 30^th, 2003, 2:04pm

Here's another way:

Find the height of the tree, then convert the tree into a heap-like tree (in an array), indicating which elements are null. Caveat: this takes time O( exp(height of tree) ), bad for a poorly balanced tree.

Now print out the heap-tree, ignoring empty spots.

Title: Re: CS: Binary Tree Print
Post by Johan on Jan 24^th, 2007, 5:28am

on 08/01/02 at 13:20:21, Jonathan the Red wrote:

Well, the below works...

Code:

...but it takes O(n log n) to complete. Can it be done more efficiently?

It is actually O(n), not O(n log n). And it's much more memory effiecient than the queuing solutions (O(n)). But only if the tree is balanced.

(For a totally unbalanced tree (with just one leg) its is O(n²) and uses O(n) memory (for the return stack).)

Why is it O(n) and not O(N log n)?

For level one: 1 node is checked.
For level two: 1+2 nodes
For level three: 1+2+4 nodes
...
For level log(N): 1+2+...+N/2

As you can see every new level uses more than twice the time of the previous level, and consequently more time than all the lower levels taken together! (I leave the formal proof to someone less rusty.)

Thus the final level takes more than half the total time.

The final level takes only O(n) time (visiting every node once).

Thus the total time is less than 2*O(n) which is of course O(n)

OK, not a very neat proof.... But it's been a long time. :P

Comments? Anyone can do it nicer?