How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Connect next pointers for each tree level

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given the root of a binary tree where each node has fields `left`, `right`, and `next` (initially `null`). For every node, set its `next` pointer to the node immediately to its right on the same level. If there is no node to the right, set `next = null`. Constraints/requirements: - The tree is not necessarily perfect or complete. - Aim for O(n) time. - Use O(1) extra space beyond the recursion/iteration variables (i.e., do not use a queue for BFS). Return the root after populating all `next` pointers.

Quick Answer: Evaluates understanding of binary tree traversal, in-place pointer manipulation, and time-space trade-offs by requiring population of sibling pointers across each level while meeting O(n) time and O(1) extra space constraints.

You are given a binary tree where every non-null node conceptually has four fields: `val`, `left`, `right`, and `next` (initially `null`). Set each node's `next` pointer to the node immediately to its right on the same level. If there is no such node, its `next` pointer should remain `null`. The tree is not necessarily perfect or complete. For this coding problem, the input tree is provided as a level-order array using heap-style indexing: for a node at index `i`, its left child is at `2*i + 1` and its right child is at `2*i + 2`. Missing nodes are represented by `None`. Because pointer-based trees are hard to compare directly in automated tests, return a flat serialization of the tree *after* connecting `next` pointers. Serialize level by level by following only `next` pointers, and append the string `'#'` after each level. Example: - Input: `[1, 2, 3, 4, 5, None, 7]` - After linking: `1 -> null`, `2 -> 3 -> null`, `4 -> 5 -> 7 -> null` - Output: `[1, '#', 2, 3, '#', 4, 5, 7, '#']` Aim for `O(n)` time and `O(1)` auxiliary space for the pointer-connection step.

Constraints

0 <= len(values) <= 100000
-10^9 <= values[i] <= 10^9 for every non-None value
The tree uses heap-style array indexing with `None` placeholders for missing nodes
The linking step should run in O(n) time
Do not use a BFS queue; use O(1) auxiliary space for connecting pointers

Examples

Input: []

Expected Output: []

Explanation: An empty tree has no levels, so the serialized result is empty.

Input: [1]

Expected Output: [1, '#']

Explanation: There is only one node, and it has no neighbor on its level.

Input: [1, 2, 3, 4, 5, None, 7]

Expected Output: [1, '#', 2, 3, '#', 4, 5, 7, '#']

Explanation: Level 1: 1. Level 2: 2 -> 3. Level 3: 4 -> 5 -> 7.

Input: [1, 2, 3, 4, None, None, 5]

Expected Output: [1, '#', 2, 3, '#', 4, 5, '#']

Explanation: The nodes 4 and 5 must be connected across different parents on the same level.

Input: [1, 2, 3, None, 4, 5, None, None, None, 6]

Expected Output: [1, '#', 2, 3, '#', 4, 5, '#', 6, '#']

Explanation: This sparse tree verifies that the algorithm correctly finds the next available child when nodes are missing.

Hints

Once one level is connected, you can traverse that entire level using `next` pointers instead of a queue.
While scanning the current level, build the next level's linked list using a dummy head and a moving tail pointer.

Quick Overview

Evaluates understanding of binary tree traversal, in-place pointer manipulation, and time-space trade-offs by requiring population of sibling pointers across each level while meeting O(n) time and O(1) extra space constraints.