Java BFS and DFS - 4 Solutions
\n\t//DFS\n\t//Time Complexity : O(n), where n is the number of elements in root\n\t//Space Complexity : O(log n), for recursion stack of a perfect BST\n\tpubli
```\n\t//DFS\n\t//Time Complexity : O(n), where n is the number of elements in root\n\t//Space Complexity : O(log n), for recursion stack of a perfect BST\n\tpublic Node connect(Node root) {\n        if(root == null)\n            return root;\n        dfs(root);\n        return root;\n    }\n    \n    private void dfs(Node root) {\n        // base\n        if(root.left == null)\n            return;\n        \n        root.left.next = root.right;\n        dfs(root.left);\n        if(root.next != null)\n            root.right.next = root.next.left;\n        dfs(root.right);\n    }\n```\n```\n\t//DFS\n\t//Time Complexity : O(n), where n is the number of elements in root\n\t//Space Complexity : O(log n), for recursion stack of a perfect BST\n\tpublic Node connect1(Node root) {\n        if(root == null)\n            return root;\n        conn(root.left, root.right);\n        return root;\n    }\n    \n    private void conn(Node left, Node right) {\n        if(left == null)\n            return;\n        \n        left.next = right;\n        conn(left.left, left. right);\n        conn(left.right, right.left);\n        conn(right.left, right.right);\n    }\n```\n```\n    //BFS\n\t//Time Complexity : O(n), where n is the number of elements in root\n\t//Space Complexity : O(1)\n\tpublic Node connect2(Node root) {\n        if(root == null)\n            return root;\n        \n        Node level = root;\n        while(level.left != null) {\n            Node curr = level;\n            while(curr != null) {\n                curr.left.next = curr.right;\n                if(curr.next != null)\n                    curr.right.next = curr.next.left;\n                curr = curr.next;\n            }\n            level = level.left;\n        }\n        return root;\n    }\n```\n```\n\t//BFS using Queue\n\t//Time Complexity : O(n), where n is the number of elements in root\n\t//Space Complexity : O(n), for queue\n\tpublic Node connect3(Node root) {\n\t\tif(root == null)\n\t\t\treturn root;\n\t\tQueue<Node> q = new LinkedList<>();\n\t\tq.offer(root);\n\n\t\twhile(!q.isEmpty()) {\n\t\t\tint size = q.size();\n\t\t\tNode prev = q.poll();\n\t\t\tif(prev.left != null) {\n\t\t\t\tq.offer(prev.left);\n\t\t\t\tq.offer(prev.right);\n\t\t\t}\n\t\t\tfor(int i=1; i<size; i++) {\n\t\t\t\tNode curr = q.poll();\n\t\t\t\tprev.next = curr;\n\t\t\t\tif(curr.left != null) {\n\t\t\t\t\tq.offer(curr.left);\n\t\t\t\t\tq.offer(curr.right);\n\t\t\t\t}\n\t\t\t\tprev = curr;\n\t\t\t}\n\t\t}\n\t\treturn root;\n\t}
['Depth-First Search', 'Breadth-First Search', 'Queue', 'Java']