import java.util.ArrayDeque;
import java.util.Stack;
import java.util.HashSet;
import java.util.ArrayList;

public class Tree
{
    static int sum;

    private static class TreeNode
    {
        private TreeNode left, right;
        private char data;
        private static char id = 'a';
        private int depth, height, localMax;

        public TreeNode(char x)
        {
            data = x;
            depth = -1;
        }

        public void setLeft(TreeNode n)
        {
            left = n;
        }

        public void setRight(TreeNode n)
        {
            right = n;
        }

        public String toString()
        {
            return Character.toString(data);
        }

        public char value()
        {
            return data;
        }

        public void branch(int depth)
        {
            if(depth <= 0)
               return;

            this.left = new TreeNode(++id);
            this.right = new TreeNode(++id);

            this.left.branch(depth - 1);
            this.right.branch(depth - 1);

            /*
            if(this.data == 'c')
                this.right.branch(3);
            */

        }

        public void _print(String soFar)
        {
            if(this.right != null)
                this.right._print(soFar + " .. ");

            System.out.println(soFar + this);

            if(this.left != null)
                this.left._print(soFar + " .. ");
        }

        public void inOrder()
        {

            if(this.left != null)
                this.left.inOrder();

            System.out.print(this + " ");

            if(this.right != null)
                this.right.inOrder();
        }

        public void preOrder()
        {
            System.out.print(this + " ");

            if(this.left != null)
                this.left.preOrder();

            if(this.right != null)
                this.right.preOrder();
        }

        public void postOrder()
        {
            if(this.left != null)
                this.left.postOrder();

            if(this.right != null)
                this.right.postOrder();

            System.out.print(this + " ");
        }

        public void levelOrder()
        {
            ArrayDeque<TreeNode> q = new ArrayDeque<TreeNode>();
            TreeNode curr;

            q.add(this);

            while( ! q.isEmpty())
            {
                curr = q.remove();
                System.out.print(curr + " ");

                if(curr.left != null)
                    q.add(curr.left);

                if(curr.right != null)
                    q.add(curr.right);
            }
        }

        public void printDepths(String soFar)
        {
            if(this.right != null)
                this.right.printDepths(soFar + " .. ");

            System.out.println(soFar + this + "("+Integer.toString(depth)+")");

            if(this.left != null)
                this.left.printDepths(soFar + " .. ");

        }

        public void printHeights(String soFar)
        {
            if(this.right != null)
                this.right.printHeights(soFar + " .. ");

            System.out.println(soFar + this + "("+Integer.toString(height)+")");

            if(this.left != null)
                this.left.printHeights(soFar + " .. ");

        }

        public void calcDepths(int depth)
        {
            this.depth = depth;

            if(this.left != null)
                this.left.calcDepths(depth + 1);

            if(this.right != null)
                this.right.calcDepths(depth + 1);
        }

        public void calcHeights()
        {
            if(this.left == null && this.right == null)
            {
                this.height = 0;
                return;
            }

            this.left.calcHeights();
            this.right.calcHeights();

            this.height = 1 + Math.max(this.left.height, this.right.height);
        }

        public void _calcHeights()
        {
            Stack<TreeNode> s = new Stack<TreeNode>();
            HashSet<TreeNode> r = new HashSet<TreeNode>();

            TreeNode node = this;

            s.push(node);
            r.add(node);

            while(! s.isEmpty())
            {
                node = s.peek();

                TreeNode leftChild = node.left;
                TreeNode rightChild = node.right;

                if(leftChild == null && rightChild == null)
                {
                    node.height = 0;
                    s.pop();
                    continue;
                }

                if(leftChild != null && ! r.contains(leftChild))
                {
                    s.push(leftChild);
                    r.add(leftChild);
                    continue;
                }

                if(rightChild != null && ! r.contains(rightChild))
                {
                    s.push(rightChild);
                    r.add(rightChild);
                    continue;
                }

                int left = (leftChild == null) ? -1 : leftChild.height;
                int right = (rightChild == null) ? -1 : rightChild.height;

                node.height = 1 + Math.max(left, right);
                s.pop();
            }
        }

        public int maxPath()
        {
            if(this.left == null && this.right == null)
                return 0;

            int maxPath = 0;

            if(this.left != null)
                maxPath += 1 + this.left.height;

             if(this.right != null)
                maxPath += 1 + this.right.height;

            int left = this.left.maxPath();
            int right = this.right.maxPath();

            return Math.max(maxPath, Math.max(left,right));
        }
    }

    private TreeNode root;

    public void inOrderPrint()
    {
        root.inOrder();
    }

    public void preOrderPrint()
    {
        root.preOrder();
    }

    public void postOrderPrint()
    {
        root.postOrder();
    }

    public void levelOrderPrint()
    {
        root.levelOrder();
    }

    private Tree(char data)
    {
        root = new TreeNode(data);
    }

    public void print()
    {
        root._print("");
    }

    public void printDepths()
    {
        root.calcDepths(0);
        root.printDepths("");
    }

    public void printHeights()
    {
        root._calcHeights();
        root.printHeights("");
    }

    public int maxPath()
    {
        root._calcHeights();
        return root.maxPath();
    }

    public TreeNode root()
    {
        return root;
    }

    public Tree(int depth)
    {
        root = new TreeNode('a');
        root.branch(depth);
    }

    public void getPathsFromLeft(TreeNode root, String soFar,
        ArrayList<String> list)
    {
        if(root == null)
            return;

        if(root.right != null)
            getPathsFromLeft(root.right, root.data + soFar, list);

        list.add(root.data + soFar);

        if(root.left != null)
            getPathsFromLeft(root.left, root.data + soFar, list);
    }

    public void getPathsFromRight(TreeNode root, String soFar,
        ArrayList<String> list)
    {
        if(root == null)
            return;

        if(root.right != null)
            getPathsFromRight(root.right, soFar + root.data, list);

        list.add(soFar + root.data);

        if(root.left != null)
            getPathsFromRight(root.left, soFar + root.data, list);
    }

    public void printPathsFromNode(TreeNode root)
    {
        if(root == null)
            return;

        int counter = 0;

        ArrayList<String> left = new ArrayList<String>();
        getPathsFromLeft(root.left, "", left);

        ArrayList<String> right = new ArrayList<String>();
        getPathsFromRight(root.right, "", right);

        for(String r : right)
            counter++;//System.out.println(root.data + r);

        counter++;//System.out.println(root);

        for(String s : left)
            counter++;//System.out.println(s + root.data);

        for(String r : right)
            for(String s : left)
                counter++;//System.out.println(s + root + r);

        //System.out.println(counter);
        sum += counter;
    }

    public void printPaths()
    {
        _printPaths(root);
    }

    public void _printPaths(TreeNode root)
    {
        printPathsFromNode(root);

        if(root.left != null)
            _printPaths(root.left);

        if(root.right != null)
            _printPaths(root.right);
    }

    public static void main(String[] args)
    {
        Tree tree = new Tree(5);
        //tree.print();

        /*
        System.out.println("\n\ninorder:");
        tree.inOrderPrint();

        System.out.println("\n\npreorder:");
        tree.preOrderPrint();

        System.out.println("\n\npostorder:");
        tree.postOrderPrint();

        System.out.println("\n\nlevelorder:");
        tree.levelOrderPrint();

        System.out.println("\n\ndepths");
        tree.printDepths();

        System.out.println("\n\nheights");
        tree.printHeights();

        System.out.println("\n\nmaxpath = " + tree.maxPath());
        */

        tree.printPaths();
        System.out.println(sum);
    }
}