<jupyter_start><jupyter_text>116. Populating Next Right Pointers in Each NodeProblem: [Link](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:<jupyter_code>from typing import Optional

# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: Node = None, right: Node = None, next: Node = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next<jupyter_output><empty_output><jupyter_text>Using BFS with a queue to store nodes to visit next.<jupyter_code>def connect(root: Optional[Node]) -> Optional[Node]:
    if root is None:
        return root
    
    to_visit = []
    nodes = [root]
    prev = None
    
    while nodes:
        current = nodes.pop(0)
        if prev:
            prev.next = current
        if current.left:
            to_visit.append(current.left)
        if current.right:
            to_visit.append(current.right)
        prev = current
        
        if len(nodes)==0:
            prev = None
            nodes = to_visit
            to_visit = []
            
    return root<jupyter_output><empty_output><jupyter_text>Without using a queue. `Next` of a node can be used for traversal as in a linked list.<jupyter_code>def connect(root: 'Optional[Node]') -> 'Optional[Node]':
    if root is None:
        return root
    
    cur = root
    nxt = cur.left
    
    while cur.left:
        cur.left.next = cur.right
        
        if cur.next:
            cur.right.next = cur.next.left
            cur = cur.next
        else:
            # This is the end of one level of the tree. We have to move to the left-most node at the next level.
            cur = nxt
            nxt = nxt.left
            
    return root<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08720330237358101, 'fraction_numerical': 0.0030959752321981426, 'mean_word_length': 2.0925039872408293, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 15, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '657053', 'license': 'Apache-2.0', 'n_tokens_mistral': 582, 'n_tokens_neox': 575, 'n_words': 185, 'path': 'leetcode/116_binary_tree_next_node.ipynb', 'repo_name': 'Kaushalya/algo_journal', 'size': '1938'}