Tree Edit Distance - Left-Most-Descendant Method

/**
 * mht Dec 19, 2011
 * reference Tim Henderson and Steve Johnson's test_tree.py
 * Tree.java is rewrite it into Java code.
 */

package org.mht.ted;

import java.util.*;

public class Tree {
    private Node _root = null;
//    private int _id = -1;
    private LinkedList<Node> _nodes = null;
    private  LinkedList<Integer> _lmds = null;
    private Node[] _keyRoots = null;

    public Tree(Node root) {
        _root = root;
        _nodes = new LinkedList<Node>();
        _lmds = new LinkedList<Integer>();
        LinkedList<Pair> stack = new LinkedList<Pair>();
        LinkedList<Pair> pstack = new LinkedList<Pair>();
        stack.add(new Pair(root, new LinkedList<Integer>()));
        int porder = 0;
        while (stack.size() > 0) {

            Pair p = (Pair)stack.removeLast();
            Node n = p.getNode();
            LinkedList<Integer> anc = p.getAncIDs();
            setid(n, porder);
            if (n.isLeaf()) {
                //stack.add(new Pair(n, anc));
                pstack.add(new Pair(n, anc));
                //return;
            }
            else {

                for (Node c: n.getChildren()) {
                    LinkedList<Integer> a = new LinkedList(anc);
                    a.addFirst(n.getid());
                    stack.addLast(new Pair(c, a));
                    }
                pstack.addLast(new Pair(n, anc));
                porder += 1;
                }
        }

        //System.out.println("Here?");

        int i = 0;

        HashMap lmds = new HashMap();
        while (pstack.size() > 0) {

            Pair p = (Pair)pstack.removeLast();
            Node n = p.getNode();
            LinkedList<Integer> anc = p.getAncIDs();
            _nodes.add(n);
            System.out.println(n.getValue());
            int lmd;
            if (n.isLeaf()) {
                lmd = i;
                for (int a : anc)
                    if (!(lmds.containsKey(a)))
                        lmds.put(a, i);
                    else
                        break;
            }
            else
                lmd = (Integer)lmds.get(n.getid());
            //System.out.print(lmd);
            _lmds.addLast(lmd);
            i += 1;
            }
        }

    public void setid(Node n, int id) {
        n.setid(id);
    }

    public Node getRoot() {
        return _root;
    }

    public LinkedList<Node> getNodes() {
        return _nodes;
    }

    public int getNodeCount() {
        int sum = 1;
        Node[] nodes = this.getRoot().getChildren();
        for (Node d : nodes) {
            sum += d.getNumOfDescendants();
        }
        return sum;
    }
    public  LinkedList<Integer> getLmds() {
        return _lmds;
    }

    public static void main(String[] args) {
        Node f = new Node("root", "f");
        Node d = new Node("left", "d");
        Node e = new Node("right", "e");
        Node a = new Node("lleft", "a");
        Node c = new Node("lright", "c");
        Node b = new Node("ldescendant", "b");

        c.addChild(b);
        d.addChild(a);
        d.addChild(c);
        f.addChild(d);
        f.addChild(e);
        Tree T = new Tree(f);
        LinkedList<Node> nodes = T.getNodes();

        for (Node n: nodes) {
            System.out.print(n.getValue());
        }
        System.out.println();
        LinkedList<Integer> lmds = T.getLmds();
        for (int i: lmds)
            System.out.print(i);
    }

    /**
     * A pair is a tuple(root, children) where root is the current
     * node and children is list of the node's child nodes from left to right.
     * @author mht
     *
     */
    class Pair {
        private Node _node = null;
        private LinkedList<Integer> _ancIDs = null;

        public Pair(Node root, LinkedList<Integer> ancIDs) {
            _node = root;
            _ancIDs = ancIDs;
        }
        public Node getNode() {
            return _node;
        }
        public LinkedList<Integer> getAncIDs() {
            return _ancIDs;
        }
    }

}