APT: Drawing Trees

Class

public class DrawTree { public String[] draw(int[] parents, String[] names) { // fill in code here } }

Problem Statement

Given a tree, you are to return a representation of that tree as a String[]. The tree will be specified by a int[], where element i gives the index of the parent of node i (indexed from 0). Exactly one element of this int[] will be -1, corresponding to the root of the tree. Element i of the int[] corresponds to element i of names, which gives the name of node i.

The String[] you return should have the root on the first line. Following the root, add elements to the return one subtree at a time. The subtrees should be sorted by the indices of their roots and drawn in the same way as the whole tree. However, the root of each subtree should be indented two more characters than its parent. After indenting, each node should be indicated by a plus '+', a minus '-', and then the name of the node from names. The plusses of siblings should be connected by vertical pipes '|' as shown in the examples. For example, the tree given by the input:

parents = {-1,0,1,1,0,0,5,5}

names = {"Root","SubB","LEAF1","LEAF2","LEAF3","SubA","LEAF4","LEAF5"}
would result in the following return.
+-Root
  +-SubB
  | +-LEAF1
  | +-LEAF2
  +-LEAF3
  +-SubA
    +-LEAF4
    +-LEAF5

See the examples for more illustrations of exactly how this works.

Constraints

Examples

  1. 
    {-1,0,1,1,0,0,5,5}
    
    {"Root","SubB","LEAF1","LEAF2","LEAF3","SubA","LEAF4","LEAF5"}
    
    Returns: 
    {"+-Root",
     "  +-SubB",
     "  | +-LEAF1",
     "  | +-LEAF2",
     "  +-LEAF3",
     "  +-SubA",
     "    +-LEAF4",
     "    +-LEAF5" }
    
    

  2. 
    {1,2,3,4,5,6,-1}
    
    {"A","B","C","D","E","F","G"}
    
    Returns: 
    {"+-G",
     "  +-F",
     "    +-E",
     "      +-D",
     "        +-C",
     "          +-B",
     "            +-A" }
    
    

  3. 
    {1,2,3,4,6,6,-1}
    
    {"A","B","C","D","E","F","G"}
    
    Returns: 
    {"+-G",
     "  +-E",
     "  | +-D",
     "  |   +-C",
     "  |     +-B",
     "  |       +-A",
     "  +-F" }
    
    

  4. 
    {6,2,3,4,5,6,-1}
    
    {"A","B","C","D","E","F","G"}
    
    Returns: 
    {"+-G",
     "  +-A",
     "  +-F",
     "    +-E",
     "      +-D",
     "        +-C",
     "          +-B" }
    
    
  5. 	   
    {-1,0,1,1,2,2,3,3,0,8,8,9,9,10,10}
    
    {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O"}
    
    Returns: 
    {"+-A",
     "  +-B",
     "  | +-C",
     "  | | +-E",
     "  | | +-F",
     "  | +-D",
     "  |   +-G",
     "  |   +-H",
     "  +-I",
     "    +-J",
     "    | +-L",
     "    | +-M",
     "    +-K",
     "      +-N",
     "      +-O" }