Populating Next Right Pointers in Each Node — LeetCode 116 Python Solution
MediumTreeDepth-First SearchBreadth-First SearchLinked ListBinary Tree
- Problem
- #116
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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: struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node.
Example
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}Python solution
Python
"""
# 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
"""
class Solution:
def connect(self, root: "Optional[Node]") -> "Optional[Node]":
if root is None:
return root
q = deque([root])
while q:
p = None
for _ in range(len(q)):
node = q.popleft()
if p:
p.next = node
p = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return rootComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 116. Populating Next Right Pointers in Each Node is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 116. Populating Next Right Pointers in Each Node?
- LeetCode 116. Populating Next Right Pointers in Each Node is rated Medium on LeetCode.
- What is the time complexity of LeetCode 116. Populating Next Right Pointers in Each Node?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 116. Populating Next Right Pointers in Each Node?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 116. Populating Next Right Pointers in Each Node cover?
- LeetCode 116. Populating Next Right Pointers in Each Node is tagged Tree, Depth-First Search, Breadth-First Search, Linked List and Binary Tree on LeetCode.