[UnSolved] Traversing Trees problem

[RllyNew2Java]

[color=white]000000000[/color]9
[color=white]00000000[/color]/[color=white]0[/color]\
[color=white]0000000[/color]11[color=white]0[/color]34
[color=white]0000000[/color]/[color=white]000[/color]/[color=white]0[/color]\
[color=white]000000[/color]12[color=white]00[/color]32[color=white]0[/color]23
[color=white]0000000[/color]\
[color=white]0000000[/color]13

[JosAH]

Can you please tell in ordinary words what exactly that transformation is about? I, for one, don't understand it from your example.

kind regards,

Jos

[JosAH]

Correct me if I'm wrong:

- you don't change the structure of the (binary?) tree, you just swap the payload of the nodes;
- you reverse every path (the payload of the nodes) starting from the rightmost path.

Am I correct?

kind regards,

Jos

[JosAH]

Yes Exactly !! Structure is the same, only values of the nodes changes.

Ok, lemme think ... use an ordinary depth first traversal but pass a list of some sort to store the current path from the root to a leaf; when a leaf is reached reverse the payloads in all the nodes in the list; something like this:

(warning: untested code ahead)

public void traverse(Node node, List<Node> path) {
   if (node != null) { // if we haven't fallen off the tree
      list.add(node);
      if (node.left == null && node.right == null) // it's a leaf
         swapPayloads(path);
      else {
         traverse(node.right, path); // right first, left last
         traverse(node.left, path);
      }
      list.remove(list.size()-1); // remove last node from the path
   }
}

The swap method looks like this:

public void swapPayloads(List<Node> path) {
   for (int i= 0, j= path.size(); i < --j; i++) {
      T payload= path.get(i).payload;
      path.get(i).payload= path.get(j).payload;
      path.get(j).payload= payload;
   }
}

I think this should do it (give or take a few typos ;-) You start the entire shebang like this:

traverse(root, new ArrayList<Node>());

Note that we don't (and can't) use that list afterwards anymore (it is empty again anyway).

kind regards,

Jos

[tim]

Hi RllyNew2Java. ;)

I've created a solution for your problem by implementing simple binary tree and using a stack to do the reversals.
The example program

package trees;

public class Main {
    public static void main(String[] args) {
        Node root = new Node(23);
        root.setLeft(new Node(12)); 		
        root.setRight(new Node(34)); 		
        root.getLeft().setLeft(new Node(11)); 		
        root.getLeft().getLeft().setRight(new Node(9)); 				
        root.getRight().setLeft(new Node(13)); 		
        root.getRight().setRight(new Node(32));
        [COLOR="Navy"]Stack<Node> leaves = new Stack<Node>();
        root.leavesRightToLeft(leaves);
        for (Node next : leaves) {
            next.reverse();
        }[/COLOR]
        root.inOrder();
    }
    
}

The binary tree

package trees;

public class Node<T> {
    protected Node<T> left = null;
    protected Node<T> right = null;
    protected Node<T> parent = null;
    protected T value;
    protected int level = 0;
    
    public Node() {
        
    }
    
    public Node(Node<T> left, Node<T> right, T value) {
        this.setLeft(left);
        this.setRight(right);
        this.setValue(value);
    }
    
    public Node(T value) {
        this.setValue(value);
    }
    
    public void inOrder() {
        if (getLeft() != null) getLeft().inOrder();
        for (int i = 1; i <= level; i++) System.out.print(" ");
        System.out.println(getValue());
        if (getRight() != null) getRight().inOrder();
    }
    
[COLOR="Navy"]    public void leavesRightToLeft(Stack<Node<T>> stack) {
        if (right != null) right.leavesRightToLeft(stack);
        if (left != null) left.leavesRightToLeft(stack);
        if (left == null && right == null) stack.push(this);
    }
    
    public void reverse() {
        // we'll use a stack for reversing
        Stack<T> stack = new Stack<T>();
        // traverse to the root and push all values onto the stack
        Node<T> finger = this;
        while (finger != null) {
            stack.push(finger.value);
            finger = finger.parent;
        }
        // traverse to the root and pop all values from the stack
        finger = this;
        while (finger != null) {
            finger.value = stack.pop();
            finger = finger.parent;
        }
    }[/COLOR]

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
        left.setParent(this);
        left.level = level + 1;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
        right.setParent(this);
        right.level = level + 1;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node<T> parent) {
        this.parent = parent;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }
    
    public String toString() {
        return value.toString();
    }
}

A simple stack

package trees;

import java.util.*;

public class Stack<T> extends Vector<T> {
    public Stack() {
    }
    
    public void push(T value) {
        add(value);
    }
    
    public T pop() {
        return remove(size() - 1);
    }
    
    public T peek() {
        return get(size() - 1);
    }
}

Use this opportunity to learn. This is the purpose of studying algorithms and data structures. Plagiarize at own loss.

[JosAH]

I'm having problems with the swap method, I don't understand the To-Do part in the for loop.... What is

 T payload= path.get(i).payload;

and the .payload ??

A node has a left and right pointer and a field named 'payload' which has a type T (I don't know anything about its type). That little method reverses the payloads for all the nodes in that list. So if the payloads were A, B, C (in that order), the payloads will be C, B, A after the reversal.

kind regards,

Jos

[JosAH]

I've created a solution for your problem by implementing simple binary tree and using a stack to do the reversals.

You algorithm fills a stack from scratch each time you reach a leaf node; that is quite inefficient for, say, neighbouring leafs (the stack will be the same except for the last entry). My version simply adjusts a stack when necessary (it is passed as an additional parameter to the recursive traversal method). Your version also needs a parent pointer per node.

kind regarards,

Jos

[tim]

You algorithm fills a stack from scratch each time you reach a leaf node; that is quite inefficient for, say, neighbouring leafs (the stack will be the same except for the last entry). My version simply adjusts a stack when necessary (it is passed as an additional parameter to the recursive traversal method). Your version also needs a parent pointer per node.

kind regarards,

Jos

I see. :) Didn't read your solution before hand. Was still fun to solve! :p

[tim]

Thanks alot for your help, I learned alot from both solutions :) ...

It's our pleasure RllyNew2Java. ;)