Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

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

Posted on 2016-10-24
6
Medium Priority
?
162 Views
Last Modified: 2016-10-31
 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(")");
        }
    }

Open in new window


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
Comment
Question by:SunnyX
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
6 Comments
 
LVL 9

Expert Comment

by:James Bilous
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

by:SunnyX
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

by:
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()

Open in new window

0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:SunnyX
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();
        LinkedList<Node<E>> output = new LinkedList();
        if (n == null) {
            return output;
        }
        queue.add(n);
        while (!queue.isEmpty()) {
            Node<E> node = queue.remove();
            output.add(node);
            if (left(node) != null) queue.add(left(node));
            if (right(node) != null) queue.add(right(node));
        }
        return output;
    }

Open in new window


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

Expert Comment

by:James Bilous
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

by:SunnyX
ID: 41867012
thx
0

Featured Post

Build and deliver software with DevOps

A digital transformation requires faster time to market, shorter software development lifecycles, and the ability to adapt rapidly to changing customer demands. DevOps provides the solution.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
The viewer will learn how to implement Singleton Design Pattern in Java.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
Suggested Courses

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

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

Join & Ask a Question