import java.util.ArrayList;

public class TNode {

    private int data;
    private int height = 0;

    private ArrayList<TNode> children;

    public TNode(int data, ArrayList<TNode> children) {
        this.data = data;
        this.children = children;
    }

    public int getHeight() {
        if (children == null)
            return 0;

        if (height != 0)
            return height;

        int max = -1;
        for (TNode t : children)
            if (t != null)
                if (t.getHeight() > max)
                    max = t.getHeight();

        return height = max + 1;
    }

    public void listAll() {
        listAll(0);
    }

    public void listAll(int depth) {
        for (int i = 0; i < depth; i++)
            System.out.print(" ");

        System.out.println(data + ":" + getHeight());
        if (children != null)
            for (TNode t : children)
                if (t != null)
                    t.listAll(depth + 1);
    }

    public ArrayList<Integer> makeList() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        listAll(list);
        return list;
    }

    public void listAll(ArrayList<Integer> list) {
        list.add(data);
        if (children != null)
            for (TNode t : children)
                if (t != null)
                    t.listAll(list);
    }

    public boolean contains(int x) {
        if (data == x)
            return true;

        if (children != null)
            for (TNode t : children)
                if (t != null)
                    if (t.contains(x))
                        return true;

        return false;
    }

    public static void main(String ... args) {
       ArrayList<TNode> tl = new ArrayList<TNode>();
       tl.add(null); tl.add(null); tl.add(null);
       TNode tA = new TNode(3, tl);

       TNode tB = new TNode(1, null);


       tl = new ArrayList<TNode>();
       tl.add(tA); tl.add(tB); tl.add(null);
       TNode tC = new TNode(4, tl);

       TNode tD = new TNode(1,null);

       tl = new ArrayList<TNode>();
       tl.add(tD);
       TNode tE = new TNode(5,tl);

       tl = new ArrayList<TNode>();
       tl.add(tE); tl.add(tC);
       TNode tRoot = new TNode(9,tl);

       tRoot.listAll();

        System.out.println(tRoot.contains(3));
        System.out.println(tRoot.contains(6));

        System.out.println(tRoot.makeList());
    }

}