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 Take-home Project rounds at TikTok.

What role is this question designed for?

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

Compute widest level span in a binary tree

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given a binary tree, define the width of a level as the number of positions between the leftmost and rightmost non-empty nodes at that depth when nodes are assigned complete-binary-tree indices (root at 1, left child = 2i, right child = 2i+ 1). Compute the maximum width across all levels. Implement a function (e.g., int maxLevelSpan(TreeNode* root)) that returns this value. Describe an O(n) approach, explain how you would prevent index overflow for very deep trees, and analyze time and space complexity.

Quick Answer: This question evaluates understanding of binary tree traversal, positional indexing in a complete binary tree, and handling integer overflow while computing level widths.

Given a binary tree, the *width* of a level is the number of positions between the leftmost and rightmost non-empty nodes at that depth, counting the nulls in between (but not the trailing/leading nulls outside that range). Formally, assign each node a complete-binary-tree index: the root gets index 1, and a node with index `i` gives its left child index `2*i` and its right child index `2*i + 1`. The width of a level is `(rightmost index - leftmost index + 1)` over the non-empty nodes on that level. Return the maximum width across all levels. The tree is provided as a level-order array `nodes` (LeetCode style): `nodes[0]` is the root, and `null` marks a missing node. Children that would hang off a `null` parent are simply absent from the array. An empty array (or a tree whose root is `null`) has width 0. Implement `maxLevelSpan(nodes)` returning the maximum level width. Key discussion points the interviewer expects: - An O(n) approach (BFS or DFS), visiting each node once. - How to prevent index overflow for very deep trees: rather than carrying the raw complete-tree index (which doubles each level and overflows a 64-bit integer past ~63 levels), subtract the leftmost index of each level from every node before computing the next level's child indices. The width is invariant under this shift, so the answer is unchanged while indices stay small. - Time and space complexity.

Constraints

0 <= number of nodes <= 3000
Node values fit in a 32-bit signed integer (only the structure matters, not the values).
The answer (maximum width) fits in a 32-bit signed integer.
nodes is given in level-order with null marking missing nodes; an empty array means an empty tree (answer 0).

Examples

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

Expected Output: 4

Explanation: Level 0: [1] width 1. Level 1: [3,2] width 2. Level 2: nodes 5,3,9 sit at complete-tree positions for 3's children (4,5) and 2's children (6,7); 3 has no right child and 2 has no left child, so present positions span from 5's slot to 9's slot = 4.

Input: ([1, 3, 2, 5, None, None, 9, 6, None, 7],)

Expected Output: 7

Explanation: The widest level is the bottom one, where the leftmost node (6, descended from 5) and the rightmost node (7, descended from 9) are 7 positions apart counting the empty slots between them.

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

Expected Output: 2

Explanation: Level 1 has two nodes [3,2] giving width 2. Level 2 has only node 5 (3's left child), width 1. Maximum is 2.

Input: ([1],)

Expected Output: 1

Explanation: A single root node — the only level has width 1.

Input: ([],)

Expected Output: 0

Explanation: Empty tree: there are no levels, so the maximum width is 0.

Input: ([1, None, 2, None, 3, None, 4],)

Expected Output: 1

Explanation: A right-leaning chain 1 -> 2 -> 3 -> 4. Each level contains exactly one node, so every level has width 1 and the maximum is 1 (a deep skewed tree where naive raw indices would balloon but relative re-indexing keeps them small).

Hints

The width of a level only depends on positions, not values. Assign the root index 1, and give a node at index i children 2i and 2i+1 — then a level's width is (max index - min index + 1) over its non-empty nodes.
Use BFS level by level, carrying each node's complete-tree index. For each level, the width is the last node's index minus the first node's index plus one (the queue is naturally ordered left-to-right).
To avoid overflow for deep trees, subtract the leftmost index of the current level from every node's index before computing children. The shift cancels out in the width calculation, so indices stay small while the answer is unchanged.

Quick Overview

This question evaluates understanding of binary tree traversal, positional indexing in a complete binary tree, and handling integer overflow while computing level widths.