Find Bottom Left Tree Value Using Python || Beats more than 90.0% ||
Intuition\nAccording to the provided question description, the objective is to identify the value of the leftmost node situated at the bottom level of the tree.
# Intuition\nAccording to the provided question description, the objective is to identify the value of the leftmost node situated at the bottom level of the tree. In cases where the leftmost node at the bottom level is absent, the goal is to return the value of the rightmost node associated with the specific node.\n\n\n# Approach\n\nI employed a **Breadth-First Search (BFS)** methodology for my approach. I maintained a single list of nodes containing tuples, each comprising the node value and its corresponding level. Essentially, I traversed the tree level by level and stored the nodes in this list along with their respective levels. Subsequently, I sorted the list in descending order based on the level values. The answer is determined by returning the value of the first node in the sorted list.\n\n# Complexity\n- **Time complexity**:**O(n log n)**\n \n 1. The **insertValuebyLevel** function is called recursively for each node in the tree, and for each node, a constant amount of work is done.\n\n 2. The sorting operation in the **findBottomLeftValue** function takes **O(n log n)** time, where \'n\' is the number of nodes in the tree.\n\n--> Therefore, the overall time complexity is O(n log n), where \'n\' is the number of nodes in the tree.\n\n- **Space complexity**: **O(n)**\n1. The **node_list** list is used to store tuples containing node values and their corresponding levels. In the worst case, all nodes are stored in this list.\n\n2. The recursion depth of the **insertValuebyLevel** function is equal to the height of the tree.\n\n--> Therefore, the overall space complexity is O(n), where \'n\' is the number of nodes in the tree.\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def __init__(self):\n        self.node_list = [] # Used to store the all the node values with its level\n \n\n    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n        answer = self.insertValuebyLevel(root, 0)\n        # Below line is used to sort the node_list in decreasing order with the value of levels.\n        # Wwhere tuples\' 0th index is value of node and 1st index will consists the value by its level.\n        sorted_node_list = sorted(self.node_list, key=lambda x: x[1], reverse=True)\n        return sorted_node_list[0][0]\n\n    def insertValuebyLevel(self,root, level):\n        # param root: It is used to get the current node.\n        # param level: It is used to get the level of current node\n        if root:\n            self.node_list.append((root.val, level)) # Add the value of current node with its level\n            level = level+1\n            if root.left:\n                self.insertValuebyLevel(root.left, level) # Call the function recursively until the value of left of node is not None\n            if root.right:\n                self.insertValuebyLevel(root.right, level) # Call the function recursively until the value of right of node is not None\n        return \n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Recursion', 'Sorting', 'Binary Tree', 'Python3']