Reverse a String in Java

I recently asked about how to reverse a String using java.
there are couple of ways for doing this.

1. Using StringBuilder or StringBuffer. former one is the newer and it's common now. you can read more about both on StringBuilder and StringBuffer. they are almost doing same thing.
2. not using option 1...:).  by saying that i mean like traversing the given string, character by character and just save it in reverse order from end toward the beginning. 

 Here is the code for both:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

package reverseString; public class Reverse { public static String reverseV1 (String input) { StringBuilder reversed = new StringBuilder(input.length()); for (int i=input.length()-1; i>=0 ;i--) { reversed.append(input.charAt(i)); } return reversed.toString(); } public static String reverseV2 (String input) { String reversed =""; for (int i=input.length()-1; i>=0;i--) { reversed = reversed + input.charAt(i); } return reversed; } public static void main(String[] args) { System.out.println ("\"super\" in reverse (using V1): " + reverseV1("super")); System.out.println ("\"super\" in reverse (using V2): " + reverseV2("super")); } }

Hope this helps.

Set Operations using ArrayList

I implemented set operations using only ArrayList and Iterator, which are part of java.util class. Java has its own Set data structure though.
The challenge for this assignment was to use only ArrayList and Iterator. I was trying to implement a BinaryTree data structure based on ArrayList and then implement my set operations on top of that. The worst case running time using ArrayList for most of the operations is O(n^2), while by using BinaryTree they can be done in O(nlog n), worst case. Here I put my code using only ArrayList features. I will make another post about my BinaryTree implementation using ArrayList.
Set class:

Here is the MySet class which implements the Set class:

There was extra mark for efficient running time which I think I won't get any, since the worst case running time for my implementation is O(n^2).
My code passed all the on line tests, however if anybody finds any problem, please leave a comment.

Leo the Pamador

Reflection of a Binary Tree

    Reflection of binary tree means if you have a binary tree like following:

                     a                                                                                 a
                  /      \                              becomes like this                  /      \
                b         c                                                                      c        b
              /    \      /   \                                                                  /    \     /   \
            d     e    f     g                                                                g     f   e    d

                       
There are 2 approaches to this problem 1- using stack 2- recursively swap sub trees
I explain both and give Java code for second approach.

1.Using Stack
     If you have recursion, you almost always can do the same job using stack. steps to produce reflection of a binary tree is:

1- Push the node in the stack
2- Pop the node from stack and if it has childes swap them
3- Push the left child and right child after swap
4- do theses steps until stack becomes empty which means you visited all nodes

example:

stack: push 'a'

pop 'a' then swap 'b' and 'c'.

stack: push 'c'. push 'b'.

pop 'b' then swap it childes, 'e' and 'd'

stack: push 'd'. push 'e'

pop 'e' which doesn't have children so return.

pop 'd' which doesn't have children so return.

stack : only contains 'c' now

continue...

pop 'c' and swap its children.

stack: push 'g'. push 'f''

pop 'f'' which doesn't have children so return.

pop 'g' which doesn't have children so return.

stack is empty now so finish.

2- Recursive method

     For operations on binary tree most of the times using recursion is a good idea.

with recursion, reflection happens in place which means the original tree replace with reflected tree.recursion is shorter than first method.

imagine you have method called reflect(Node<E> node)

which accept Node<E> of the binary tree. we call this method in our caller method with root of binary tree.

steps are:

1-if root is empty return
2- call reflect for left sub tree
3- call reflect for right sub tree
4- swap left and right sub trees using temp variable...temp is the same type of node.

Java code:
Testing:
To test operation on binary tree, the best approach in my opinion is to use Graphvis website which shows you visual output based on your input. you can write a method to traverse your tree after and before reflection and generate a  Graphvis  dot file or its accepted input data, then you can use  Graphvis  to see the output is what it is supposed to be.
I give a Java code for generating dot output to use in  Graphvis  .
output is in String format, however you can write the output to a .dot file and then load it on  Graphvis  website.

Java code for generating Graphvis .dot data:

p.s: When using this generator you should add the following line before the actual data inside the curly braces to give you right visual output:    graph [ordering="out"];

p.s.s: You can also use queue instead of stack.