Algorithm problem

[Guest]

I have an algorithm question and don't know how to do it nicely.
Write a function to print nodes of binary tree, for each leaf node, print nodes from root node to leaf node.

For example, the following binary tree has 4 leaf nodes.
30
25 36
39 40 10 64

The resulting of print should be :
30, 25, 39
30, 25, 40
30, 36, 10
30, 36, 64

 

[Kevin Aubuchon]

Are the nodes supposed to be sorted? Or what order do you need them printed?
Usually going through a tree is a recursive procedure, and a node is only
accessed (i.e. printed) once. Why do you keep printing 30? A node that is a
leaf to the level above is a root to the level below. Here is a simple
algorithm.

curr = head;
printFunc( curr);

printFunc( root)
{
if root.left
printFunc(root.left);

print root;

if root.right
printFunc(root.right);
}

I think your tree would print as follows (I didn't code this, just a quick
run through in my head).

39 25 40 30 10 36 64

HTH,
kevin aubuchon

I have an algorithm question and don't know how to do it nicely.
Write a function to print nodes of binary tree, for each leaf node, print

nodes from root node to leaf node.

 

[Hilton]

I have an algorithm question and don't know how to do it nicely.
Write a function to print nodes of binary tree, for each leaf node, print

nodes from root node to leaf node.

For example, the following binary tree has 4 leaf nodes.
30
25 36
39 40 10 64

The resulting of print should be :
30, 25, 39
30, 25, 40
30, 36, 10
30, 36, 64

printTree (tree, new Stack ());


void printTree (Tree root, Stack path)
{
// Are we at a leaf?
if ((root.left == null) && (root.right == null))
{
// It's a leaf, print the path and the leaf
print (path);
print (root);
}
else
{
// Not a leaf, so remember this node as part of the path and keep
going...
nodes.push (root);

// Stop at the light, look both ways, look both ways again...
if (root.left != null)
{
printTree (root.left, path);
}
if (root.right != null)
{
printTree (root.right, path);
}

// Well, we're done with this node, it's no longer prt of the path
node.pop ();
}
}

Off the top of my head, untested etc. Hope this helps.

Hilton

 

[Tom Dacon]

Briefly, you'd do this with a recursive depth-first traversal of the tree.
For each child of the root, pass an argument to the traversal routine that
would be a string containing the node number of the root. Each child would
add a comma and a space and its own node number, and recursively pass that
along to its child nodes, unless it had no children (i.e., was a leaf node),
in which case it would print out the string.

Thus, in the example given, the root node would pass "30" to its direct
children, nodes 25 and 36 would pass (respectively) "30, 25" and "30, 36" to
each of their children, and each of the leaf nodes would add their own node
numbers to the string they received and print it out.

Sorry I don't have time to write and include the code.
Tom Dacon
Dacon Software Consulting

I have an algorithm question and don't know how to do it nicely.
Write a function to print nodes of binary tree, for each leaf node, print

nodes from root node to leaf node.