I am currently attempting to write a single recursive method (per instruction) whereas the items in a binary tree are displayed in a horizontal hierarchical manner (level order traversal).

The UML describes the method as:
levelOrderTraversal(TreeNode<T> tree, Integer indent)
- tree: a node in the binary tree
- indent: describes the indentation required for the node

The following is a example of the output that should be produced when levelOrderTraversal is called:

199
          77
     64
          62
60
          40
     38
          22
               11

As mentioned, the instructions require that the method strictly use recursion (and thus implicitly am not allowed to use an iterative method using a queue/stack data structure). I've searched textbooks and Google, but I am honestly stumped. Any advice on how I can create this method would be truly appreciated.

Thanks, JP

Edited 5 Years Ago by jonpadre: Typo

Looking at the output one line at a time, starting from the top (ie as you would print it) the pattern we see is

some node's left sub-tree (if any)
the node itself
the nodes right sub-tree (if any)

then the sub-trees are the same (recursively), and each time you recurse the indentation increases.

You already have the hard part of the method signature, so just start and see how it goes.

Thanks James for the advice!

So the pattern appears to begin as an in-order traversal, however the output needs to be reversed. For example, using the sample BST above, the output recursively prints the nodes in the following order "11, 22, 38, 40, 60, 62, 64, 77, 199". What still has me confused how to modify the in-order algorithm so that the output is displayed in the following order, "199, 77, 64, 62 ..."

In advance, thanks again for the advice!

So the pattern appears to begin as an in-order traversal, however the output needs to be reversed. For example, using the sample BST above, the output recursively prints the nodes in the following order "11, 22, 38, 40, 60, 62, 64, 77, 199". What still has me confused how to modify the in-order algorithm so that the output is displayed in the following order, "199, 77, 64, 62 ..."

In advance, thanks again for the advice!

Please disregard the quoted post. I figured out the descending in-order traversal. Here's the psuedocode (without the indentations yet):

levelOrderTraversal(tree.rightNode); // some node's right subtree
        System.out.printf("%s  ", tree.data); // print the node
        levelOrderTraversal(tree.leftNode);  // some node's left subtree

Now I just need to figure out the indentation and this method will be complete. Thanks guys!

This article has been dead for over six months. Start a new discussion instead.