CheckSubtree (_4_10)

CheckSubtree.java

import java.util.ArrayList;
import java.util.List;

/**
 * Check Subtree: T1 and T2 are two very large binary trees, with T1 much bigger than T2.
 * Create an algorithm to determine if T2 is a subtree of T1.
 * A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2.
 * That is, if you cut off the tree at node n, the two trees would be identical.
 * <p>
 * Hints: #4, #77, #78, #37, #37
 */
public class CheckSubtree {
    public static void main(String[] args) {
        Node n6 = new Node(24, null, null, null);
        Node n5 = new Node(13, null, null, null);

        Node n4 = new Node(8, null, null, null);
        Node n3 = new Node(3, null, null, null);

        Node n2 = new Node(20, n5, n6, null);
        Node n1 = new Node(5, n3, n4, null);
        Node r = new Node(10, n1, n2, null);

        Node n66 = new Node(24, null, null, null);
        Node n55 = new Node(13, null, null, null);
        Node n22 = new Node(20, n55, n66, null);

        Node n100 = new Node(24, null, null, null);
        Node n101 = new Node(13, null, null, null);
        Node n102 = new Node(21, n101, n100, null);

        System.out.println(solution1(r, n22)); // expected output: true
        System.out.println(solution1(r, n102)); // expected output: false
        System.out.println();

        System.out.println(solution2(r, n22)); // expected output: true
        System.out.println(solution2(r, n102)); // expected output: false
        System.out.println();

        System.out.println(solution3(r, n22)); // expected output: true
        System.out.println(solution3(r, n102)); // expected output: false
        System.out.println();

        System.out.println(solution4(r, n22)); // expected output: true
        System.out.println(solution4(r, n102)); // expected output: false
    }

    public static boolean solution1(Node n1, Node n2) {
        List<Node> l1 = new ArrayList<>();
        List<Node> l2 = new ArrayList<>();

        solution1(n1, l1);
        solution1(n2, l2);

        int counter = 0;
        int firstIndex = 0;

        for (int i = 0; i < l2.size(); i++) {
            System.out.print(".");
            int num = l1.indexOf(l2.get(i));
            if (counter == 0) {
                firstIndex = num;
            }
            counter += num;
        }

        return counter == firstIndex * l2.size() + l2.size();
    }

    private static void solution1(Node n, List<Node> l) {
        System.out.print(".");
        if (n == null) {
            return;
        }

        l.add(n);
        solution1(n.getLeft(), l);
        solution1(n.getRight(), l);
    }

    public static boolean solution2(Node n1, Node n2) {
        if (n1 == null || n2 == null) {
            return false;
        }

        List<List<Integer>> list = new ArrayList<>();
        list.add(new ArrayList<>());
        list.add(new ArrayList<>());

        solution2(n1, n2, list);
        return list.get(0).size() == list.get(1).size() && !list.get(0).isEmpty() && !list.get(1).isEmpty();
    }

    public static void solution2(Node n1, Node n2, List<List<Integer>> list) {
        System.out.print(".");
        if (n1 == null || n2 == null) {
            return;
        }
        list.get(1).add(1);

        if (n2.getValue() == n1.getValue()) {
            list.get(0).add(1);
            solution2(n1.getLeft(), n2.getLeft(), list);
            solution2(n1.getRight(), n2.getRight(), list);
        } else {
            list.get(1).remove(0);
            solution2(n1.getLeft(), n2, list);
            solution2(n1.getRight(), n2, list);
        }
    }

    public static boolean solution3(Node n1, Node n2) {
        if (n1 == null || n2 == null) {
            return false;
        }

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();

        solution3(n1, sb1);
        solution3(n2, sb2);

        return sb1.indexOf(sb2.toString()) != -1;
    }

    private static void solution3(Node n, StringBuilder sb) {
        System.out.print(".");
        if (n == null) {
            sb.append("X");
            return;
        }

        sb.append(n.getValue());
        solution3(n.getLeft(), sb);
        solution3(n.getRight(), sb);
    }

    public static boolean solution4(Node t1, Node t2) {
        if (t2 == null) return true;
        return subTree(t1, t2);
    }

    public static boolean subTree(Node r1, Node r2) {
        System.out.print(".");
        if (r1 == null) {
            return false;
        } else if (r1.getValue() == r2.getValue() && matchTree(r1, r2)) {
            return true;
        }
        return subTree(r1.getLeft(), r2) || subTree(r1.getRight(), r2);
    }

    public static boolean matchTree(Node r1, Node r2) {
        System.out.print(".");
        if (r1 == null && r2 == null) {
            return true;
        } else if (r1 == null || r2 == null) {
            return false;
        } else if (r1.getValue() != r2.getValue()) {
            return false;
        } else {
            return matchTree(r1.getLeft(), r2.getLeft()) && matchTree(r1.getRight(), r2.getRight());
        }
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;
    private Node parent;

    public Node(int value, Node left, Node right, Node parent) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }

    public Node getParent() {
        return parent;
    }

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

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value + " ";
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        return value == node.value;
    }

}