> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/07-15-2022-116.-populating-next-right-pointers-in-each-node.md).

# 07/15/2022 116. Populating Next Right Pointers in Each Node

116\. Populating Next Right Pointers in Each Node

Method 1: use bfs. traverse each level of tree. use a queue to push each level nodes inside it. Then iterate the node in the queue, if the index is less than the size - 1, we make the node's next to point to the top of the queue.

Time O(N) Space O(N)

Method 2: Using previously established next pointers.  Set leftmost = root. While leftmost is not null, we set head to the leftmost, then we set head.left.next = head.right. If the head.next is not null, we set head.right.next = head.next.left. Then set head = head.next. Finally set leftmost = leftmost.left.

**Time O(N)**

Space O(1)