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

## All 3 Replies

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.

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 ..."

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 ..."

``````levelOrderTraversal(tree.rightNode); // some node's right subtree