import java.util.*;

class BinaryTree {
    private Node root;

    public static void main(String[] args){
	Node a = new Node("a");
	Node b = new Node("b");
	Node c = new Node("c");
	Node d = new Node("d");
	Node e = new Node("e");

	BinaryTree bt = new BinaryTree(a);
	
	d.setLeft(e);

	b.setLeft(d);

	a.setLeft(b);
	a.setRight(c);
	
	System.out.println("height="+height(a));
	System.out.println("balanced="+(bt.balanced() ? "true" : "false"));
	
	LinkedList leaves = bt.leaves();
	Iterator it = leaves.listIterator();
	while (it.hasNext()){
	    System.out.println(it.next());
	}
    }

    public BinaryTree(Node root){
	this.root = root;
    }

    public boolean balanced(){
	return balanced(root); // true if this tree is balanced.
    }

    static int height(Node t){
	int hl,hr;

	if (t==null) return 0;
	hl = height(t.left);
	hr = height(t.right);
	return hl>hr ? hl+1 : hr+1;
    }

    public static boolean balanced(Node t){
	if (t==null) return true;
	return balanced(t.left) && balanced(t.right) && Math.abs(height(t.left)-height(t.right))<=1;
    }

    public LinkedList leaves(){
	LinkedList lst = new LinkedList();
	leaves(root,lst);
	return lst;
    }  
    
    public static void leaves(Node t,LinkedList lst){
	if (t==null) return;
	if (t.left==null && t.right==null) lst.addFirst(t.getVal());
	leaves(t.left,lst);
	leaves(t.right,lst);
    }
}

class Node {
    Object elm;
    Node left,right;
    public Node(Object elm){
	this.elm = elm;
    }
    public void setLeft(Node left){
	this.left = left;
    }
    public void setRight(Node right){
	this.right = right;
    }
    public void setVal(Object elm){
	this.elm = elm;
    }
    public Object getVal(){
	return elm;
    }
}