ListOfDepths (_4_3)

ListOfDepths.java

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * List of Depths: Given a binary tree, design an algorithm which creates
 * a linked list of all the nodes at each depth (e.g., if you have a tree with depth 0, you'll have 0 linked lists).
 * Hints: #107, #123, #735
 */
public class ListOfDepths {
    public static void main(String[] args) {
        Node n10 = new Node("n10", null, null);

        Node n9 = new Node("n9", null, null);
        Node n8 = new Node("n8", null, null);
        Node n7 = new Node("n7", null, n10);

        Node n6 = new Node("n6", null, null);
        Node n5 = new Node("n5", null, null);

        Node n4 = new Node("n4", n8, n9);
        Node n3 = new Node("n3", n7, null);

        Node n2 = new Node("n2", n5, n6);
        Node n1 = new Node("n1", n3, n4);
        Node r = new Node("r", n1, n2);

        System.out.println(solution1(r));
        System.out.println(solution2(r));
    }

    public static ArrayList<LinkedList<Node>> solution1(Node root) {
        ArrayList<LinkedList<Node>> collector = new ArrayList<>();
        LinkedList<Node> current = new LinkedList<>();

        if (root == null) {
            return collector;
        }

        current.add(root);

        while (current.size() > 0) {
            collector.add(current);

            LinkedList<Node> parents = current;
            current = new LinkedList<>();

            for (Node n : parents) {
                if (n.getLeft() != null) {
                    current.add(n.getLeft());
                }
                if (n.getRight() != null) {
                    current.add(n.getRight());
                }
            }
        }

        return collector;
    }

    public static ArrayList<LinkedList<Node>> solution2(Node root) {
        ArrayList<LinkedList<Node>> collector = new ArrayList<>();
        solution2(root, collector, 0);
        return collector;
    }

    private static void solution2(Node root, ArrayList<LinkedList<Node>> collector, int level) {
        if (root == null) {
            return;
        }

        LinkedList<Node> list;

        if (collector.size() == level) {
            list = new LinkedList<>();
            collector.add(list);
        } else {
            list = collector.get(level);
        }

        list.add(root);
        solution2(root.getLeft(), collector, level + 1);
        solution2(root.getRight(), collector, level + 1);
    }

}

class Node {
    private String name;
    private Node left;
    private Node right;

    public Node() {
    }

    public Node(String name, Node left, Node right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    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 String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

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