SRM 731 Div 1 Easy

TreesAndBrackets.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Tree {
    List<Tree> branches;

    Tree() {
        this.branches = new ArrayList<>();
    }

    void addBranch(Tree tree) {
        branches.add(tree);
    }
}

public class TreesAndBrackets {

    public String check(String t1, String t2) {
        Tree tree1 = buildTree(t1);
        Tree tree2 = buildTree(t2);

        return checkTree(tree1.branches, tree2.branches) ? "Possible" : "Impossible";
    }

    private boolean checkTree(List<Tree> branches1, List<Tree> branches2) {
        if (branches2.isEmpty()) {
            return true;
        }

        if (branches1.isEmpty()) {
            return false;
        }

        if (checkTree(branches1.get(0).branches, branches2.get(0).branches)) {
            if(checkTree(branches1.subList(1, branches1.size()), branches2.subList(1, branches2.size()))) {
                return true;
            }
        }

        return checkTree(branches1.subList(1, branches1.size()), branches2);
    }

    private Tree buildTree(String t) {
        Tree head = new Tree();
        Deque<Tree> treeStack = new ArrayDeque<>();

        Tree current = head;
        for (char c : t.toCharArray()) {
            if (c == '(') {
                treeStack.addLast(current);
                current = new Tree();
            }
            if (c == ')') {
                Tree parent = treeStack.removeLast();
                parent.addBranch(current);
                current = parent;
            }
        }

        return head;
    }
}