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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

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

Delete nodes in linked list and binary tree

Q: Delete nodes in linked list and binary tree

This question evaluates proficiency in mutable data structure operations, specifically linked list node removal and binary tree node replacement/deletion, requiring knowledge of traversal, pointer/reference manipulation, and edge-case handling.

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve **two short coding tasks**. You may assume standard node definitions: - **Singly linked list node:** `val`, `next` - **Binary tree node:** `val`, `left`, `right` ## Task A — Remove the Nth node from the end of a linked list Given the head of a singly linked list and an integer `n`, remove the **n-th node from the end** of the list and return the new head. **Requirements** - `1 <= n <= length(list)` - Aim for `O(L)` time where `L` is the list length, and `O(1)` extra space. ## Task B — Delete a node from a binary tree and reconnect Given the root of a **binary tree (not necessarily a BST)** and an integer `key`, delete **one** node whose value equals `key` and return the (possibly new) root. To keep the tree structure valid after deletion, perform deletion using this rule: 1. Find the node `X` with value `key`. 2. Find the **deepest, rightmost** node in the tree `D`. 3. Replace `X.val` with `D.val`. 4. Delete node `D` from its parent by setting the corresponding child pointer to `null`. **Edge cases** - If `key` is not found, return the original root. - If the tree has only one node and it matches `key`, return `null`. **Complexity target:** `O(N)` time, `O(N)` space is acceptable (e.g., BFS queue), where `N` is the number of nodes.

Quick Answer: This question evaluates proficiency in mutable data structure operations, specifically linked list node removal and binary tree node replacement/deletion, requiring knowledge of traversal, pointer/reference manipulation, and edge-case handling.

Part 1: Remove the Nth Node from the End of an Encoded Linked List

A singly linked list is encoded as nested Python tuples of the form `(value, next_node)`, where `next_node` is either another tuple or `None`. For example, `(1, (2, (3, None)))` represents the linked list `1 -> 2 -> 3`. Given the encoded head of a linked list and an integer `n`, remove the `n`-th node from the end of the list and return the new encoded head. Your algorithm should follow linked-list logic rather than relying on random access.

Constraints

Let `L` be the number of nodes in the list.
`1 <= L <= 10^5`
`1 <= n <= L`
Node values are integers in the range `[-10^9, 10^9]`

Examples

Input: ((1, (2, (3, (4, (5, None))))), 2)

Expected Output: (1, (2, (3, (5, None))))

Explanation: The 2nd node from the end is `4`, so the result is `1 -> 2 -> 3 -> 5`.

Input: ((1, None), 1)

Expected Output: None

Explanation: Single-node list: deleting the 1st node from the end removes the only node.

Input: ((1, (2, None)), 2)

Expected Output: (2, None)

Explanation: The node to remove is the head because `n` equals the list length.

Input: ((10, (20, (30, None))), 1)

Expected Output: (10, (20, None))

Explanation: Deleting the 1st node from the end removes the tail node `30`.

Hints

A dummy node before the head makes deleting the first real node much easier.
Use two pointers: move one pointer `n` steps ahead, then move both pointers together until the front pointer reaches the end.

Part 2: Delete a Node from a Binary Tree Using Deepest-Rightmost Replacement

A binary tree is encoded as a level-order Python list, where missing children are represented by `None`. For example, `[1, 2, 3, None, 4]` means node `2` has no left child and has right child `4`. Given the encoded root of a binary tree and an integer `key`, delete one node whose value equals `key` using this exact rule: 1. Find the target node `X`. 2. Find the deepest, rightmost node `D` in the tree. 3. Copy `D.val` into `X.val`. 4. Remove the original deepest-rightmost node `D` from its parent. If `key` does not exist, return the original tree. If the tree has one node and it matches `key`, return an empty list. For deterministic behavior, if multiple nodes contain `key`, delete the first one found in level-order traversal. Return the resulting tree in trimmed level-order form, with unnecessary trailing `None` values removed.

Constraints

`0 <= N <= 10^4`, where `N` is the number of non-`None` nodes in the tree
Tree values are integers in the range `[-10^9, 10^9]`
The tree is not necessarily a BST
An `O(N)` time solution is expected
`O(N)` auxiliary space is allowed

Examples

Input: ([1, 2, 3, 4, 5, 6], 3)

Expected Output: [1, 2, 6, 4, 5]

Explanation: Node `3` is replaced by deepest-rightmost node `6`, and the original `6` is removed.

Input: ([1], 1)

Expected Output: []

Explanation: The tree has one node and it matches `key`, so the result is an empty tree.

Input: ([1, 2, 3], 9)

Expected Output: [1, 2, 3]

Explanation: The key does not exist, so the original tree is returned unchanged.

Input: ([10, 11, 12, None, 13], 11)

Expected Output: [10, 13, 12]

Explanation: The deepest-rightmost node is `13`, which replaces `11`, and the original `13` node is removed.

Input: ([], 5)

Expected Output: []

Explanation: Deleting from an empty tree should still return an empty tree.

Hints

A breadth-first search can simultaneously find the target node, the deepest-rightmost node, and each node's parent.
After replacing the target value, be careful to delete the original deepest-rightmost node from its parent, not the target node itself.

Quick Overview

This question evaluates proficiency in mutable data structure operations, specifically linked list node removal and binary tree node replacement/deletion, requiring knowledge of traversal, pointer/reference manipulation, and edge-case handling.