0

I am looking for an algorithm to compare two trees.

I have this class in Java

public class TreeNodeDSP {

  TreeNodeDSP parent;
  List<TreeNodeDSP> children;
  NodeDSP value;

  public TreeNodeDSP(TreeNodeDSP parent) {
    this.parent = parent;
    children = new ArrayList<>();
  }

  public TreeNodeDSP(TreeNodeDSP parent, NodeDSP value) {
    this.parent = parent;
    children = new ArrayList<>();
    this.value = value;
  }

  public void addChild(TreeNodeDSP node) {
    if (node != null && node.getValue() != null) {
      if (children.stream().noneMatch(child -> Objects.equals(child.getValue(), node.getValue()))) {
        children.add(node);
      }
    }
  }

  public TreeNodeDSP getParent() {
    return parent;
  }

  public void cleanChildren() {
    children = new ArrayList<>();
  }

  public int getChildrenCount() {
    return children.size();
  }

  public TreeNodeDSP getChildrenAt(int position) {
    if (children.size() > position && position > -1) {
      return children.get(position);
    }
    return null;
  }

  public List<TreeNodeDSP> getChildren() {
    return children;
  }

  public NodeDSP getValue() {
    return value;
  }

  public boolean isLeaf() {
    return children.isEmpty();
  }

}

Now, I have an algorithm to populate my Tree (TreeNodeDSP) and facing problem performing operations based on Automatically populate Tree (calculating some conditions),

I populate manually my Tree and works.

I need to discover what is the difference in my Tree (manually Populated, and Automatically) in its nodes (internally), not only says are different Trees. When some node/leaf is different I need to print its contents.

But, I don't know how to begin with the comparison Algorithm.

  • Start by performing a tree traversal and generate a textual (and visual) representation of the tree. This will let you see the trees you are dealing with. Based on what you see you will need to consider how you are going to compare the trees. I'd recommend looking at the leaves first. They are the simplest tree to compare, and then consider each parent node from there iteratively till you have figured out how to compare the entire tree. – Kain0_0 Mar 2 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.