new_contents: # Time:  O(n)
  # Space: O(h)
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def printTree(self, root):
          """
          :type root: TreeNode
          :rtype: List[List[str]]
          """
          def getWidth(root):
              if not root:
                  return 0
              return 2 * max(getWidth(root.left), getWidth(root.right)) + 1
  
          def getHeight(root):
              if not root:
                  return 0
              return max(getHeight(root.left), getHeight(root.right)) + 1
              
          def preorderTraversal(root, level, left, right, result):
              if not root:
                  return
              mid = left + (right - left) / 2
              result[level][mid] = str(root.val)
              preorderTraversal(root.left, level+1, left, mid-1, result)
              preorderTraversal(root.right, level+1, mid+1, right, result)
  
          h, w = getHeight(root), getWidth(root)
          result = [[""] * w for _ in xrange(h)]
          preorderTraversal(root, 0, 0, w-1, result)
          return result
  
subject: Create print-binary-tree.py