LeetCode : 655 Print Binary Tree | Python with Depth First Search Solution

 

LeetCode : https://leetcode.com/problems/print-binary-tree/description/

YouTube Link : 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    res = []
    height = 0
    
    def printTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[str]]
        """

        # Find height of tree to determine 2D List dimensions 
        height_of_tree = self.calculate_height(root)
        m =  height_of_tree # Numbers of rows
        n = 2**m -1  # Number of Columns
        
        # Init 2D list with "" empty values     
        res = [[""]*n for _ in range(m)]

        # Init low and high values based on list size 
        low = 0 
        high = n

        def helper ( root , rowCounter , low  , high ):
            if root is None:
                return None 

            # Alway calculate mid position for placing root value
            mid = (low+high) // 2
            res[rowCounter][mid] = str(root.val)

            # Traverse Tree with 
            left = helper(root.left , rowCounter+1 , low , mid-1)
            right = helper(root.right , rowCounter+1 , mid+1, high )

        helper(root , 0 , low , high )    
        return  res 

    
    # Calculate Height Of Tree 
    def calculate_height(self,root):
        if root is None :
            return 0 
        left = self.calculate_height(root.left)
        right = self.calculate_height(root.right)

        return max(left, right) + 1