(0)
                (0                                  0)
       (0                0)                (0                0)
   (0       0)       (0       0)       (0       0)       (0       0)
(0    0) (0    0) (0    0) (0    0) (0    0) (0    0) (0    0) (0    0)

import java.util.*;

/**
 * @program: leetcode
 * @description:
 * @author: CJ Sun
 * @create: 2019-12-06 14:40
 **/

public class TreePrinter {

    public static void main(String[] args) {
        int height = 6;
        int maxLen = 4;

        Map<String, String> dataMap = new HashMap<>();

        generateData(maxLen, height, 1, "", dataMap);

        print(dataMap, height, maxLen);
    }

    private static void generateData(int len, int height, int level, String seq, Map<String, String> dataMap) {
        String num = "";
        for (int i = 0; i < len - 1; i++) {
            num += "0";
        }

        if (seq.endsWith("l")) {
            dataMap.put(seq, "(" + num);
        } else if (seq.endsWith("r")) {
            dataMap.put(seq, num + ")");
        } else {
            dataMap.put(seq, "(" + num + ")");
        }

        if (height == level) {
            return;
        }

        generateData(len, height, level + 1, seq + 'l', dataMap);
        generateData(len, height, level + 1, seq + 'r', dataMap);
    }

    public static void print(Map<String, String> dataMap, int height, int maxLen) {
        List<String> leafs = new ArrayList<>();

        generateLeafs(height, 1, "", leafs);

//        Map<String, String> dataMap = new HashMap<>();
//        generateData(height, 1, "", dataMap);

        Map<String, Integer> positionMap = new TreeMap<>();

        setLeafPosition(leafs, maxLen, positionMap);

        List<String> parents = new ArrayList<>(positionMap.keySet());

        // set position for parent nodes with leaf positions
        for (int i = height - 2; i >= 0; i--) {
            for (String p : parents) {
                p = p.substring(0, i);
                positionMap.put(p, (positionMap.get(p + "l") + positionMap.get(p + "r")) / 2);
            }
        }

        Map<Integer, List<String>> keys = new HashMap<>();

        // group all the paths by its level, sort nodes of each nodes from left the right
        for (int i = 0; i < height; i++) {
            for (String key : positionMap.keySet()) {
                if (key.length() != i) {
                    continue;
                }

                if (!keys.containsKey(i)) {
                    keys.put(i, new ArrayList<>());
                }

                keys.get(i).add(key);
            }

            Collections.sort(keys.get(i));
        }

        // print all the nodes
        for (int i = 0; i < height; i++) {
            List<String> ks = keys.get(i);

            int pre = 0;
            for (int j = 0; j < ks.size(); j++) {
                int position = positionMap.get(ks.get(j));

                for (int k = 0; j == 0 && k < position - 1; k++) {
                    System.out.print("-");
                }

                for (int k = 0; j != 0 && k < position - pre - 1; k++) {
                    System.out.print("-");
                }

                if (!dataMap.containsKey(ks.get(j))) {
                    for (int k = 0; k < maxLen; k++) {
                        System.out.print("-");
                    }
                } else {
                    System.out.print(dataMap.get(ks.get(j)));
                }

                pre = position + maxLen - 1;
            }

            for (int j = 0; j < 1; j++) {
                System.out.println();
            }
        }
    }

    private static void generateLeafs(int height, int level, String seq, List<String> leafs) {
        if (height == level) {
            leafs.add(seq);

            return;
        }

        generateLeafs(height, level + 1, seq + 'l', leafs);
        generateLeafs(height, level + 1, seq + 'r', leafs);
    }

    private static void setLeafPosition(List<String> leafs, int maxLen, Map<String, Integer> positionMap) {
        int pos = 1;
        for (int i = 0; i < leafs.size() / 2; i++) {
            positionMap.put(leafs.get(i * 2), pos);

            pos += 2 * maxLen + 2;
            positionMap.put(leafs.get(i * 2 + 1), pos);

            pos += maxLen + 1;
        }
    }
}