Piece together the parts of the Tree BFS traversal, focusing on various traversal methods.

Coding

Explores nodes of a tree level by level, ensuring each level is processed before moving to the next, often using a queue to manage traversal.

Tree Breadth-First Search

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# Statement

Given a #key# **perfect binary tree: A binary tree in which all the levels are completely filled with nodes, and all leaf nodes (nodes with no children) are at the same level.** #key#, where each node contains an additional pointer called `next`. This pointer is initially set to `NULL` for all nodes. Your task is to connect all nodes of the same hierarchical level by setting the `next` pointer to its immediate right node.

 The `next` pointer of the rightmost node at each level is set to NULL.

**Constraints:**
- The number of nodes in the tree is in the range $[0, 500]$.
- $-1000 \leq$ `Node.data` $\leq 1000$



# Solution

So far, you've probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

## Naive approach
The naive approach to establishing connections between nodes at the same level in a binary tree is to utilize a queue data structure and perform a level order traversal. The steps of the algorithm are given below:

1) Start with the root node of the binary tree.
2) Create an empty queue data structure to perform the breadth-first traversal.
Enqueue the root node into the queue.
3) While the queue is not empty, perform the following steps:
   - Initialize a variable, `level_size`, to the current size of the queue (number of nodes in the current level).
   - Traverse through each node in the current level (equal to `level_size`):
      - Dequeue the front node from the queue and call it the `current_node`.
      - If `i` (current index in the level) is less than `level_size - 1`, set the `next` pointer of `current_node` to the first node in the queue (front of the queue) representing the next node at the same level.
      - Enqueue the left and right children of `current_node` (if they exist) into the queue.
4) Return the root node of the modified binary tree with the connections between nodes using the `next` pointers.

The time complexity of this naive approach is $O(n)$, where $n$ is the number of nodes in the binary tree. This is because we visit each node once during the breadth-first traversal.

The space complexity of the naive approach is also $O(n)$. At any given time, the queue can store at most one-level nodes in the binary tree. The binary tree is a complete binary tree with $n/2$ nodes in the last level, which is proportional to $n$. Therefore, the space complexity is $O(n)$.

## Optimized approach using Tree Breadth-first Search

To establish connections between nodes at the same level in a binary tree, we can optimize the approach by leveraging the existing tree structure and employing a tree breadth-first search pattern. The goal is to create a linklist-like structure at each level, where each node points to its right sibling.

Instead of using an additional queue data structure, which consumes extra space, we can utilize the existing structure of the binary tree to achieve the same level-order traversal without the need for the queue.

The algorithm uses a nested while loop to traverse the tree and establish the connections:

1. First, check if the root node is NULL. If it is, return NULL, indicating an empty tree.
2. If the `root` is not `NULL`, it initializes `mostleft` as the `root` node. This variable keeps track of the leftmost node of the current level.
3.  Iterate through each level of the tree. The outer loop continues until no more levels are below (`mostleft.left` is NULL).
   - Inside the outer loop, there is an inner loop that traverses each node on the current level. It starts with the `current` variable initialized as the leftmost node of the current level.
   - Within the inner loop, the algorithm establishes the connections between nodes.
      - **First connection:** It connects the `current` node's left child to its right child by assigning `current.left.next` to `current.right`.
      - **Second connection:** If there is a next node (`current.next`) on the same level, it connects the `current` node's right child to the left child of its next node by assigning `current.right.next` to `current.next.left`.
      - After connecting the nodes on the current level, the `current` moves to the next node on the same level. This process continues until the end of the level is reached (`current` becomes `NULL`).
7. Once the inner loop completes, the `mostleft` is updated to the left child of the previous `mostleft` node. This moves the traversal down to the next level.
8. The outer loop repeats the above steps until there are no more levels below (`mostleft.left` is `NULL`).
9. Finally, the modified `root` node is returned.

Let’s look at the following illustration to get a better understanding of the solution:

Let's solve the Populating Next Right Pointers in the Each Node problem using the Tree Breadth-first Search pattern.

Solution: Populating Next Right Pointers in Each Node

Statement▼

Solution

Solution: Populating Next Right Pointers in Each Node

Statement▼

Solution