O(n) time and O(1) space Easy Intutive solution for better understanding of recursion
Intuition\n Describe your first thoughts on how to solve this problem. \nInitially, I considered a bottom-up recursion approach where I would set the next point
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nInitially, I considered a bottom-up recursion approach where I would set the next pointer during the backtracking step. However, this approach failed when connecting a node on the right to another node on its parent\'s left. This led me to devise a top-down approach, using the `next` pointer of the parent to set the next pointers of the children.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe create a helper function where we pass the node and its parent. The base case is when the node is null. Here\'s the step-by-step process:\n\nIf the node is null, we return immediately.\n\nIf the parent is not null, we set `parent->left->next` to `parent->right`.\n\nIf the parent is not null and parent->next is not null, we set `parent->right->next` to `parent->next->left`.\n\nWe then check if the `root->left` and `root->right` are not null, and recursively call the helper for both the left and right children.\n\n# Complexity\n- Time complexity:\n$$O(n)$$ \n\n- Space complexity:\n$$O(1)$$ if we ignore the recursion stack or else $$O(log(n))$$\n\n# Code\n```cpp []\n/*\n// Definition for a Node.\nclass Node {\npublic:\n    int val;\n    Node* left;\n    Node* right;\n    Node* next;\n\n    Node() : val(0), left(NULL), right(NULL), next(NULL) {}\n\n    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}\n\n    Node(int _val, Node* _left, Node* _right, Node* _next)\n        : val(_val), left(_left), right(_right), next(_next) {}\n};\n*/\n\nclass Solution {\npublic:\n    void helper(Node* root, Node* parent) {\n        if (root == NULL)\n            return;\n        if (parent != NULL)\n            parent->left->next = parent->right;\n        if (parent != NULL and parent->next != NULL)\n            parent->right->next = parent->next->left;\n        if (root->left == NULL and root->right == NULL)\n            return;\n        helper(root->left, root);\n        helper(root->right, root);\n    }\n    Node* connect(Node* root) {\n        helper(root, NULL);\n        return root;\n    }\n};\n```\n``` python3 []\n"""\n# Definition for a Node.\nclass Node:\n    def __init__(self, val: int = 0, left: \'Node\' = None, right: \'Node\' = None, next: \'Node\' = None):\n        self.val = val\n        self.left = left\n        self.right = right\n        self.next = next\n"""\n\nclass Solution:\n  def helper(self, root: \'Node\', parent: \'Node\') -> None:\n    if root is None:\n      return\n    if parent is not None:\n      parent.left.next = parent.right\n    if parent is not None and parent.next is not None:\n      parent.right.next = parent.next.left\n    if root.left is None and root.right is None:\n      return\n    self.helper(root.left, root)\n    self.helper(root.right, root)\n  \n  def connect(self, root: \'Node\') -> \'Node\':\n    self.helper(root, None)\n    return root\n\n```\n``` java []\n/*\n// Definition for a Node.\nclass Node {\n    public int val;\n    public Node left;\n    public Node right;\n    public Node next;\n\n    public Node() {}\n\n    public Node(int _val) {\n        val = _val;\n    }\n\n    public Node(int _val, Node _left, Node _right, Node _next) {\n        val = _val;\n        left = _left;\n        right = _right;\n        next = _next;\n    }\n};\n*/\n\nclass Solution {\n    private void helper(Node root, Node parent) {\n        if (root == null) return;\n        if (parent != null) parent.left.next = parent.right;\n        if (parent != null && parent.next != null) parent.right.next = parent.next.left;\n        if (root.left == null && root.right == null) return;\n        helper(root.left, root);\n        helper(root.right, root);\n    }\n\n    public Node connect(Node root) {\n        helper(root, null);\n        return root;\n    }\n}\n\n\n\n```
['Linked List', 'Tree', 'C++', 'Java', 'Python3']