Print Tree Hierarchy

http://wxx5433.github.io/print-tree-hierarchy.html

Given edges as follows, print the tree as a hierarchy.

  b -> c
  b -> d
  b -> e
  a -> f
  c -> g
  a -> b
  f -> h

To print:

  a
    f
        h
    b
        c
            g
        d
        e

Analysis

We should first define the Node class. It should contain a char value, a list of children and a parent node. Then we can preprocess the input data to create nodes for all characters.

After building the tree, we can now use dfs to traverse it. Each time we go into a deeper length, we print one more space before it.

Complexity

Time: O(M) to preprocess input data, where M is the number of input data. O(N) to print the hierarchy where N is the number of nodes.

class Node {
    char val;
    List<Node> children;
    Node parent;

    public Node(char val) {
        children = new ArrayList<Node>();
        this.val = val;
    }

    public void addChildren(Node n) {
        children.add(n);  // add child node
        n.parent = this;  // set parent node
    }
}
    public Map<Character, Node> buildList (char[][] edges) {
        Map<Character, Node> map = new HashMap<Character, Node>();
        int len = edges.length;
        for (int i = 0; i < len; ++i) {
            Node n = null;
            if (map.containsKey(edges[i][0])) {
                n = map.get(edges[i][0]);
            } else {
                n = new Node(edges[i][0]);      
            }
            map.put(edges[i][0], n); 
            Node child = null;
            if (map.containsKey(edges[i][1])) {
                child = map.get(edges[i][1]);
            } else {
                child = new Node(edges[i][1]);
                map.put(edges[i][1], child);
            }
            n.addChildren(child);  
        }
        return map;
    }

    public void print(Map<Character, Node> map) {
        Node root = null;
        for (Character c: map.keySet()) {
            // find the root node, may have several root nodes
            if (map.get(c).parent == null) {
                root = map.get(c);
                traversal(root, 0);
            }
        }
    }

    // dfs
    private void traversal(Node root, int depth) {
        if (root == null) {
            return;
        }
        // print space here
        for (int i = 0; i < depth; ++i) {
            System.out.print(" ");
        }
        System.out.println(root.val);
        for (Node child: root.children) {
            traversal(child, depth + 1);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        char[][] edges = {{'b', 'c'}, {'b', 'd'}, {'b', 'e'}, {'a', 'f'}, 
                {'c', 'g'}, {'a', 'b'}, {'f', 'h'}, {'x', 'y'}, {'y', 'z'}};
        PrintTree pt = new PrintTree();
        Map<Character, Node> map = pt.buildList(edges);
        pt.print(map);
    }