Python 4 Diffrent Solutions | BFS | DFS
1. Iterative BFS | Space:O(n)\n\n    def connect(self, root: \'Optional[Node]\') -> \'Optional[Node]\':\n        if( root == None ):\n            return root;\n
# 1. Iterative BFS | Space:O(n)\n```\n    def connect(self, root: \'Optional[Node]\') -> \'Optional[Node]\':\n        if( root == None ):\n            return root;\n        q = deque();\n        q.append(root);\n        while( len(q) > 0 ):\n            prev = None ;\n            size = len(q);\n            while(size > 0 ):\n                node = q.popleft();\n                node.next = prev;\n                prev = node;\n                if(node.right):q.append(node.right);\n                if(node.left):q.append(node.left);\n                size -= 1;\n        return root;\n```\n\n# 2.Recursive DFS | Space: O(n)\n\n```\n    def connect(self, root: \'Optional[Node]\') -> \'Optional[Node]\':\n        hmap = defaultdict(list);\n\n        def dfs(node,h):\n            if( node == None ):\n                return;\n            else:\n                hmap[h].append(node);\n                dfs(node.left,h+1);\n                dfs(node.right,h+1);\n        \n        dfs(root,0);\n        for key in hmap.keys():\n            for i in range(0, len(hmap[key])-1 ):\n                hmap[key][i].next = hmap[key][i+1]\n            hmap[key][-1].next = None\n        return root\n```\n\n# 3.Recusive DFS | Space:O(logn)\n\n```\ndef connect(self, root: \'Optional[Node]\') -> \'Optional[Node]\':\n        if( root == None ):\n            return;\n        root.next = None;\n        def dfs(node):\n            if( node == None or node.left == None ):\n                return;\n            node.left.next = node.right;\n            if(node.next):\n                node.right.next =node.next.left;\n            dfs(node.left);\n            dfs(node.right);    \n\n        dfs(root);\n        return root;\n\n```\n\n# 4. Iterative Optimized BFS or Level order traversal | O(1)\n```\n    def connect(self, root: \'Optional[Node]\') -> \'Optional[Node]\':\n        prev = root;\n        cur = root;\n        while(prev):\n            cur = prev;\n            while( cur ):\n                if(cur.left):\n                    cur.left.next = cur.right;\n                    if(cur.next):\n                        cur.right.next = cur.next.left;\n                cur = cur.next;\n            prev = prev.left;\n\n        return root;\n```
['Depth-First Search', 'Breadth-First Search', 'Python3']