Populating Next Right Pointers in Each Node II — LeetCode 117 Python Solution
MediumTreeDepth-First SearchBreadth-First SearchLinked ListBinary Tree
- Problem
- #117
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given a binary tree struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
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: "Node") -> "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 117. Populating Next Right Pointers in Each Node II 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
On a study list
This problem is on Top Interview 150.
Frequently asked questions
- How hard is LeetCode 117. Populating Next Right Pointers in Each Node II?
- LeetCode 117. Populating Next Right Pointers in Each Node II is rated Medium on LeetCode.
- What is the time complexity of LeetCode 117. Populating Next Right Pointers in Each Node II?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 117. Populating Next Right Pointers in Each Node II?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 117. Populating Next Right Pointers in Each Node II cover?
- LeetCode 117. Populating Next Right Pointers in Each Node II is tagged Tree, Depth-First Search, Breadth-First Search, Linked List and Binary Tree on LeetCode.