Solved

# Java. Convert method from recursion based to iteration based ( loop based )

Posted on 2016-10-24
Medium Priority
204 Views
`````` public void toString(NodeImpl<E> node) {
if (node == root) {
treeToString.append(root.key + "(");
}
if (node.left == nil && node.right == nil) {
if (node == node.parent.right) {
}
}
if (node.left != nil) {
if (node.left.left != nil || node.left.right != nil) {
treeToString.append(node.left.key + "(");
toString(node.left);
} else {
if (node.right != nil) {
treeToString.append(node.left.key);
} else {
treeToString.append(node.left.key + ")");
}
toString(node.left);
}
}
if (node.right != nil) {
if (node.right.left != nil || node.right.right != nil) {
if (node.left != nil) {
treeToString.append("," + node.right.key + "(");
} else {
treeToString.append(node.right.key + "(");
}
toString(node.right);
} else {
if (node.left != nil) {
treeToString.append("," + node.right.key);
} else {
treeToString.append(node.right.key);
}
toString(node.right);
}
treeToString.append(")");
}
}
``````

I need to implement toString  to represent a tree like (also each level can be a separate line):
(n1(n11(n111, n112), n12(n121, n122)))
that corresponds to tree hierarchy:
n1
n11                 n12
n111 n112      n121   n122

In addition, the method should be based on the loop. I made the method which is work correctly based on recurion. Could help me to convert this method to loop based.
Thx in advanced dear experts !
0
Question by:SunnyX
• 3
• 3

LVL 9

Expert Comment

ID: 41857208
This is essentially a depth first search that prints as it traverses the graph. Heres some pseudo code for an iterative approach: http://www.cs.toronto.edu/~heap/270F02/node36.html

It'd be easier to start from there than to try and chop up and repurpose your recursive code IMO.
0

Author Comment

ID: 41858666
Yes, indeed there is conceptual simularity with deep-first search. However, does I handle the bracket in my case ?
0

LVL 9

Accepted Solution

James Bilous earned 2000 total points
ID: 41858722
If we think about the bracket placement, it becomes apparent that they occur whenever a child node is entered or left.

This would correspond to the following points in the pseudo-code:

`````` DFS(G,v)   ( v is the vertex where the search starts )
Stack S := {};   ( start with an empty stack )
for each vertex u, set visited[u] := false;
push S, v;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
// Print '('
// Print node name
visited[u] := true;
for each unvisited neighbour w of u
push S, w;
// Print ')'
end if
end while
END DFS()
``````
0

Author Comment

ID: 41858751
Okey, this is implementation of the deep-first search in Java which is work fine for sure.
``````private List<Node<E>> breadthFirst(Node<E> n) {
Queue<Node<E>> queue = new LinkedList();
if (n == null) {
return output;
}
while (!queue.isEmpty()) {
Node<E> node = queue.remove();
if (left(node) != null) queue.add(left(node));
if (right(node) != null) queue.add(right(node));
}
return output;
}
``````

Could you please tell me how can change the code to handle brackets ?
0

LVL 9

Expert Comment

ID: 41858763
What you posted is breadth first search not depth first since it uses a queue. You need to use a stack instead for DFS.
0

Author Closing Comment

ID: 41867012
thx
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Join & Write a Comment Already a member? Login.

Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
This video teaches viewers about errors in exception handling.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
###### Suggested Courses
Course of the Month6 days, 8 hours left to enroll

#### 589 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.