dfs iterative using stack
Intuition\nThe code aims to check whether a given binary tree is balanced or not. A binary tree is considered balanced if the heights of its left and right subt
# Intuition\nThe code aims to check whether a given binary tree is balanced or not. A binary tree is considered balanced if the heights of its left and right subtrees differ by at most 1 for all nodes in the tree.\n\n# Approach\nThe code employs an iterative approach using a stack to traverse the binary tree while keeping track of the depths of the left subtrees of each node. Here\'s a step-by-step explanation of the approach:\n\n1. Initialize a stack to perform a depth-first traversal of the binary tree. Each item in the stack is a tuple containing a node and a boolean flag indicating whether the node has been visited.\n\n2. Initialize a dictionary depths to store the maximum depth of each node encountered so far. Initially, it\'s empty.\n\n3. While the stack is not empty, pop a node and its visited flag from the stack.\n\n4. If the node has been visited (i.e., the flag is True), calculate the depths of its left and right subtrees using the depths dictionary. Check if the tree rooted at this node is balanced by comparing the absolute difference between the depths of its left and right subtrees with 1. If it\'s greater than 1, return False as the tree is not balanced.\n\n5. If the node has not been visited (i.e., the flag is False), mark it as visited and push it back into the stack. Push its left and right children into the stack if they exist.\n\n6. Update the depths dictionary with the maximum depth encountered so far for this node.\n\nRepeat steps 3-6 until the stack is empty.\n\nIf the traversal completes without encountering any unbalanced nodes, return True, indicating that the tree is balanced.\n\n# Complexity\n- Time complexity:\nThe code performs a single traversal of the binary tree, visiting each node once. Therefore, the time complexity is O(N), where N is the number of nodes in the tree.\n\n- Space complexity:\nThe space complexity is O(H), where H is the height of the binary tree. This is due to the stack used for the iterative traversal and the depths dictionary, which can have at most H entries, one for each level of the tree. In the worst case, for a skewed tree, H can be equal to N, making the space complexity O(N). In a balanced tree, H is approximately log(N), resulting in a space complexity of O(log(N)).\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 isBalanced(self, root: Optional[TreeNode]) -> bool:\n        if not root:\n            return True\n        \n        stack = [[root,False]]\n        heights = defaultdict(int)\n\n        while stack:\n            x , visited = stack.pop()\n\n            if visited:\n                leftheight = heights[x.left]\n                rightheight = heights[x.right]\n\n                if abs(rightheight - leftheight) > 1:\n                    return False\n                heights[x] = max(leftheight,rightheight) + 1\n\n            else:\n                stack.append([x,True])\n                if x.right:\n                    stack.append([x.right,False])\n                if x.left:\n                    stack.append([x.left,False])\n\n        return True\n\n        \n\n        \n\n\n        \n\n            \n```
['Stack', 'Depth-First Search', 'Iterator', 'Python3']