Recursion on Trees and Graphs advice

Question

Could some one provide me examples of using recursion on an advanced data structure. I have an exam today. Preferrably I would like the example to be more difficult than fibonacci or factorial examples but easier than the tower of hanoi problem. Any advice on how to manipulate data structures with recursion is appreciated.

Answer 1

Recursive example for tree:

void action(Node root){
    if(root.left!=null)action(root.left);
    if(root.right!=null)action(root.right);
    //current node action code here
}

There are iterative functions, that have more code but are more stack friendly for your system. Depending on size of your system choose some of those. Iterative is much better if you are making something working with large structure, and depending on speed.

Check out these: link1 and Iterative approach

Its same with graphs, except you have more output branches, which make iterative approach better.

Answer 2

These are examples visits for BinaryTrees implemented with a linked structure.

public static <E> void printInorder(LinkedBTree<E> t) throws EmptyTreeException{
    if(t != null && !t.isEmpty())
        printInorder((BTPosition<E>)(t.root()));
    System.out.print("\n");
}

private static <E> void printInorder(BTPosition<E> v){
    if(v.getLeft() != null) printInorder(v.getLeft());
    System.out.print(v.element()+" ");
    if(v.getRight() != null) printInorder(v.getRight());
}

public static <E> void printPreorder(LinkedBTree<E> t) throws EmptyTreeException{
    if(t != null && !t.isEmpty())
        printPreorder((BTPosition<E>)(t.root()));
    System.out.print("\n");
}

private static <E> void printPreorder(BTPosition<E> v){
    System.out.print(v.element()+" ");
    if(v.getLeft() != null) printPreorder(v.getLeft());
    if(v.getRight() != null) printPreorder(v.getRight());
}

public static <E> void printPostorder(LinkedBTree<E> t) throws EmptyTreeException{
    if(t != null && !t.isEmpty())
        printPostorder((BTPosition<E>)(t.root()));
    System.out.print("\n");
}

private static <E> void printPostorder(BTPosition<E> v){
    if(v.getLeft() != null) printPostorder(v.getLeft());
    if(v.getRight() != null) printPostorder(v.getRight());
    System.out.print(v.element()+" ");
}

Answer 3

Depth-First Traversals:

public void preOrder(Node<T> root)
{
     if (root != null)
     {
         System.out.println(root);
         preOrder(root.leftChild);
         preOrder(root.rightChild);
     }
}


public void inOrder(Node<T> root)
{
     if (root != null)
     {
         inOrder(root.leftChild);
         System.out.println(root);
         inOrder(root.rightChild);
     }
}


public void postOrder(Node<T> root)
{
     if (root != null)
     {
         postOrder(root.leftChild);
         postOrder(root.rightChild);
         System.out.println(root);
     }
}

Here's a simple way to check for a balanced expression:

private String open  = "([<{";
private String close = ")]>}";

private boolean isOpen(char ch)
{
    return open.indexOf(ch) == -1 ? false : true;
}

private boolean isClosed(char ch)
{
    return close.indexOf(ch) == -1 ? false : true;
}

private boolean balanced(String sequence)
{
    if (sequence != null && sequence.length() > 0)
        return isBalanced(sequence, "");
    else 
        return true;
}

private boolean matches(char fromSeq, char fromStack)
{
    return open.indexOf(fromStack) == close.indexOf(fromSeq);
}


private boolean isBalanced(String seq, String stack)
{
    if (seq.length() == 0 )
    {
        return stack.length() == 0;
    }
    else
    {
        char first = seq.charAt(0);

        if (isOpen(first))
        {
            return isBalanced(seq.substring(1), first + stack);
        }
        else if (isClosed(first))
        {
            return stack.length() != 0 && matches(first, stack.charAt(0)) && isBalanced(seq.substring(1), stack.substring(1));
        }
        else
        {
            return isBalanced(seq.substring(1), stack);
        }
    }

Here's a simple way to get all permutations of some domain, ie you would calling:
permute(3,"01", ""); yields:

000 001 010 011 100 101 110 111

public void permute(int length, String domain, String result)
    {
        if (length == 0)
        {
            System.out.println(result);
        }
        else
        {
            for (int i = 0; i < domain.length(); i++)
                permute(length-1, domain, result + domain.charAt(i));
        }
    }

Finally, a simple python example for computing base^exp (while it's in python, it should be easy to understand):

def powrec(base, exp):
    if exp < 0 and base != 0:
        return powrec(1.0/base, -exp)

    if exp == 0:
        return 1

    if exp == 1:
        return base

    if exp % 2 == 0:
        return powrec(base*base, exp/2)

    else:
        return base*powrec(base*base, exp/2)