🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
IntuitionThe problem involves connecting all nodes at the same level in a perfect binary tree. Since the tree is perfect (all levels are completely filled), eac
![image.png](https://assets.leetcode.com/users/images/ce7653ec-f7e8-4b3b-8e95-121ae3383cf6_1736701401.6159008.png)


---

# **Intuition**  
The problem involves connecting all nodes at the same level in a perfect binary tree. Since the tree is perfect (all levels are completely filled), each node will have its left child, right child, and potentially a `next` sibling to its immediate right. We can utilize the tree's structure to link these nodes without requiring additional data structures.

---

# **Approach**  
1. Start at the root and use a pointer (`leftMost`) to traverse level by level.
2. For each level, traverse the nodes using another pointer (`currNode`).
3. Connect:
   - `currNode.left.next` to `currNode.right`.
   - If `currNode.next` exists, connect `currNode.right.next` to `currNode.next.left`.
4. Move `leftMost` to the leftmost node of the next level and repeat until all levels are processed.

---

# **Complexity**  
- **Time complexity:** $$O(n)$$, where $$n$$ is the number of nodes in the tree. Each node is visited once.  
- **Space complexity:** $$O(1)$$, as no additional data structures are used, apart from a few pointers.

---


```java []
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node leftMost = root;

        while (leftMost.left != null) {
            Node currNode = leftMost;

            while (currNode != null) {
                currNode.left.next = currNode.right;
                if (currNode.next != null) {
                    currNode.right.next = currNode.next.left;
                }
                currNode = currNode.next;
            }

            leftMost = leftMost.left;
        }

        return root;
    }
}
```


```python []
# Definition for a Node.
class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None

        leftMost = root

        while leftMost.left:
            currNode = leftMost

            while currNode:
                currNode.left.next = currNode.right
                if currNode.next:
                    currNode.right.next = currNode.next.left
                currNode = currNode.next

            leftMost = leftMost.left

        return root
```


```cpp []
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        Node* leftMost = root;

        while (leftMost->left) {
            Node* currNode = leftMost;

            while (currNode) {
                currNode->left->next = currNode->right;
                if (currNode->next) {
                    currNode->right->next = currNode->next->left;
                }
                currNode = currNode->next;
            }

            leftMost = leftMost->left;
        }

        return root;
    }
};
```


```dart []
class Node {
  int val;
  Node? left;
  Node? right;
  Node? next;

  Node(this.val, [this.left, this.right, this.next]);
}

class Solution {
  Node? connect(Node? root) {
    if (root == null) return null;
    Node? leftMost = root;

    while (leftMost!.left != null) {
      Node? currNode = leftMost;

      while (currNode != null) {
        currNode.left!.next = currNode.right;
        if (currNode.next != null) {
          currNode.right!.next = currNode.next!.left;
        }
        currNode = currNode.next;
      }

      leftMost = leftMost.left;
    }

    return root;
  }
}
```


```go []
type Node struct {
    Val   int
    Left  *Node
    Right *Node
    Next  *Node
}

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    leftMost := root

    for leftMost.Left != nil {
        currNode := leftMost

        for currNode != nil {
            currNode.Left.Next = currNode.Right
            if currNode.Next != nil {
                currNode.Right.Next = currNode.Next.Left
            }
            currNode = currNode.Next
        }

        leftMost = leftMost.Left
    }

    return root
}
```


```javascript []
// Definition for a Node.
function Node(val, left, right, next) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
    this.next = next === undefined ? null : next;
}

var connect = function(root) {
    if (!root) return null;
    let leftMost = root;

    while (leftMost.left) {
        let currNode = leftMost;

        while (currNode) {
            currNode.left.next = currNode.right;
            if (currNode.next) {
                currNode.right.next = currNode.next.left;
            }
            currNode = currNode.next;
        }

        leftMost = leftMost.left;
    }

    return root;
};
```

---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Breadth-First Search', 'C', 'Binary Tree', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']