/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<IList<string>> PrintTree(TreeNode root) {
        int d = FindDepth(root);
        return BuildTree(root, d);
    }

    private IList<IList<string>> BuildTree(TreeNode current, int rD)
    {
        if (rD <= 0) return null;

        IList<IList<string>> ret = new List<IList<string>>();

        if (rD == 1)
        {
            var sL = new List<string>();

            if (current == null)
            {
                sL.Add("");
            }
            else
            {
                sL.Add(current.val.ToString());
            }

            ret.Add(sL);
            return ret;
        }


        IList<IList<string>> leftT = BuildTree(current?.left, rD - 1);
        IList<IList<string>> rightT = BuildTree(current?.right, rD - 1);


        var fL = new List<string>();
        for (int i = 0; i < leftT[0].Count(); i++)
        {
            fL.Add("");
        }

        if (current == null)
        {
            fL.Add("");
        }
        else
        {
            fL.Add(current.val.ToString());
        }

        for (int i = 0; i < leftT[0].Count(); i++)
        {
            fL.Add("");
        }
        ret.Add(fL);
        for (int i = 0; i < leftT.Count(); i++)
        {
            var newL = new List<string>(leftT[i]);
            newL.Add("");
            newL.AddRange(rightT[i]);
            ret.Add(newL);
        }
        return ret;
    }

    private int FindDepth(TreeNode current)
    {
        if (current == null) return 0;
        return Math.Max(FindDepth(current.right), FindDepth(current.left)) + 1;
    }
}