Problem Description

This problem asks you to transform a deeply nested object or array by replacing all undefined values with null.

The input obj can be any JavaScript object or array that may contain nested structures at multiple levels. Your task is to traverse through the entire structure and convert every undefined value to null, while keeping all other values unchanged.

The motivation behind this problem relates to JSON serialization. When using JSON.stringify() to convert JavaScript objects to JSON strings, undefined values are handled inconsistently - they are omitted from objects but converted to null in arrays. This inconsistency can lead to unexpected behavior. By converting all undefined values to null beforehand, you ensure consistent and predictable serialization.

For example:

• Input: {"a": undefined, "b": 3} should return {"a": null, "b": 3}
• Input: [undefined, undefined] should return [null, null]
• For nested structures like {"a": {"b": undefined}, "c": 1}, the result should be {"a": {"b": null}, "c": 1}

The solution needs to recursively process all nested objects and arrays to ensure every undefined value at any depth is replaced with null.

Intuition

The key insight is that we need to visit every value in a potentially nested structure. This immediately suggests a recursive approach - when we encounter an object or array, we need to dive deeper into it before processing the current level.

Think of it like exploring a tree structure. At each node, we need to:

1. First check if the current value is itself an object (which includes arrays) - if so, we need to explore its children
2. After exploring any nested structures, check if the current value is undefined and replace it with null

The order matters here. We process nested objects first (depth-first traversal) to ensure we handle all levels of nesting. This way, when we return from a recursive call, we've already processed all the deeper levels.

For the iteration through the object, we use a for...in loop which works for both regular objects and arrays. In JavaScript, arrays are objects with numeric keys, so for...in will iterate through array indices just as it iterates through object properties.

The type check typeof obj[key] === 'object' is interesting because in JavaScript, typeof null also returns 'object'. However, this actually works in our favor - if a value is already null, we'll recursively call the function on it, but since null has no enumerable properties, the for...in loop won't execute, and we'll just return the null value unchanged.

This recursive pattern naturally handles arbitrary nesting depth - each recursive call handles one level deeper, and the recursion naturally terminates when we reach primitive values (numbers, strings, booleans) or null values that have no properties to iterate over.

Solution Approach

The implementation uses a recursive depth-first traversal to process the nested structure:

function undefinedToNull(obj: Record<any, any>): Record<any, any> {
    for (const key in obj) {
        if (typeof obj[key] === 'object') {
            obj[key] = undefinedToNull(obj[key]);
        }
        if (obj[key] === undefined) {
            obj[key] = null;
        }
    }
    return obj;
}

Let's walk through the implementation step by step:

1. Iterate through all properties: The for...in loop iterates through all enumerable properties of the object. This works for both objects and arrays since arrays in JavaScript are objects with numeric indices as keys.

2. Check for nested objects: For each property, we first check if its value is an object using typeof obj[key] === 'object'. This condition will be true for:

   • Nested objects {...}
   • Arrays [...]
   • null values (though they have no properties to iterate)

   When we find a nested object, we recursively call undefinedToNull(obj[key]) and assign the result back to obj[key]. This ensures we process all nested levels before continuing.

3. Replace undefined with null: After handling any potential nested structure, we check if the current value is undefined. If it is, we replace it with null by assigning obj[key] = null.

4. In-place modification: The function modifies the object in place rather than creating a new object. Each recursive call operates on the same object reference, directly updating values as it traverses.

5. Return the modified object: Finally, we return the modified object. Since we've been modifying it in place, this is the same object reference that was passed in, but with all undefined values replaced.

The algorithm handles edge cases naturally:

• Empty objects or arrays simply return after the loop completes with no iterations
• Primitive values at any level are left unchanged (except undefined)
• null values are preserved since the recursive call on them does nothing
• The depth of recursion is limited only by the JavaScript call stack

Time complexity: O(n) where n is the total number of properties across all nested levels. Space complexity: O(d) where d is the maximum depth of nesting (for the recursion call stack).

Example Walkthrough

Let's trace through a small example to understand how the solution works:

Input: {"a": undefined, "b": {"c": undefined, "d": 2}}

Step-by-step execution:

1. First call - undefinedToNull({"a": undefined, "b": {"c": undefined, "d": 2}})

   • Start iterating with for...in loop
   • Process key "a":
     • Check: Is obj["a"] (which is undefined) an object? No, typeof undefined is "undefined"
     • Check: Is obj["a"] undefined? Yes!
     • Action: Set obj["a"] = null
   • Process key "b":
     • Check: Is obj["b"] (which is {"c": undefined, "d": 2}) an object? Yes!
     • Action: Recursively call undefinedToNull({"c": undefined, "d": 2})

2. Second call (nested) - undefinedToNull({"c": undefined, "d": 2})

   • Start iterating with for...in loop
   • Process key "c":
     • Check: Is obj["c"] (which is undefined) an object? No
     • Check: Is obj["c"] undefined? Yes!
     • Action: Set obj["c"] = null
   • Process key "d":
     • Check: Is obj["d"] (which is 2) an object? No
     • Check: Is obj["d"] undefined? No
     • Action: No change, keep value as 2
   • Return {"c": null, "d": 2}

3. Back to first call:

   • The recursive call returns {"c": null, "d": 2}, which gets assigned to obj["b"]
   • Check: Is obj["b"] undefined? No (it's now {"c": null, "d": 2})
   • Continue to next iteration (no more keys)
   • Return {"a": null, "b": {"c": null, "d": 2}}

Final output: {"a": null, "b": {"c": null, "d": 2}}

The algorithm successfully replaced both undefined values at different nesting levels with null, while preserving the number value 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of properties/elements in the object including all nested objects and arrays.

The function visits each property in the object exactly once. For nested objects, it recursively processes them, but each property is still only visited once during the entire traversal. Therefore, if there are n total properties across all levels of nesting, the time complexity is linear.

Space Complexity: O(d) where d is the maximum depth of nesting in the object structure.

The space complexity comes from the recursive call stack. In the worst case, if we have a deeply nested object, the recursion will go d levels deep, using O(d) space for the call stack. The function modifies the object in-place rather than creating new objects, so no additional space is used for storing data beyond the recursion stack.

Note: If we consider the input size, the space complexity could also be expressed as O(n) in the worst case when the object is structured as a deeply nested chain (like {a: {b: {c: {d: ...}}}}) where the depth equals the number of properties.

Common Pitfalls

1. Incorrect Type Checking for Objects

The original TypeScript solution uses typeof obj[key] === 'object' to check for nested structures. This creates a critical bug because typeof null === 'object' in JavaScript, causing the function to attempt recursive calls on null values.

Problem Example:

const input = {"a": null, "b": undefined};
// typeof null === 'object' returns true
// Attempts to call undefinedToNull(null)
// Results in attempting to iterate over null's properties

Solution: Add an explicit null check before the recursive call:

function undefinedToNull(obj: Record<any, any>): Record<any, any> {
    for (const key in obj) {
        // Check for non-null objects
        if (obj[key] !== null && typeof obj[key] === 'object') {
            obj[key] = undefinedToNull(obj[key]);
        }
        if (obj[key] === undefined) {
            obj[key] = null;
        }
    }
    return obj;
}

2. Mutating the Original Object

The function modifies the input object in-place, which can cause unexpected side effects if the original object is used elsewhere in the code.

Problem Example:

const original = {"a": undefined, "b": {"c": undefined}};
const result = undefinedToNull(original);
console.log(original === result); // true - same object reference
// original is now modified: {"a": null, "b": {"c": null}}

Solution: Create a deep copy before modification or build a new object during traversal:

function undefinedToNull(obj: Record<any, any>): Record<any, any> {
    if (obj === null || obj === undefined) return obj;
  
    if (Array.isArray(obj)) {
        return obj.map(item => 
            item === undefined ? null : 
            (typeof item === 'object' && item !== null) ? undefinedToNull(item) : item
        );
    }
  
    if (typeof obj === 'object') {
        const result: Record<any, any> = {};
        for (const key in obj) {
            const value = obj[key];
            result[key] = value === undefined ? null :
                (typeof value === 'object' && value !== null) ? undefinedToNull(value) : value;
        }
        return result;
    }
  
    return obj;
}

3. Not Handling Arrays Properly

While for...in works for arrays, it iterates over all enumerable properties including non-numeric indices and inherited properties, which may not be desired behavior.

Problem Example:

const arr = [undefined, 1, 2];
arr.customProp = undefined;  // Adding a non-numeric property
// for...in will iterate over '0', '1', '2', and 'customProp'

Solution: Explicitly handle arrays differently using Array methods or numeric iteration:

function undefinedToNull(obj: any): any {
    if (obj === null || obj === undefined) return obj;
  
    // Handle arrays specifically
    if (Array.isArray(obj)) {
        for (let i = 0; i < obj.length; i++) {
            if (typeof obj[i] === 'object' && obj[i] !== null) {
                obj[i] = undefinedToNull(obj[i]);
            }
            if (obj[i] === undefined) {
                obj[i] = null;
            }
        }
        return obj;
    }
  
    // Handle objects
    if (typeof obj === 'object') {
        for (const key in obj) {
            if (obj.hasOwnProperty(key)) {  // Only process own properties
                if (typeof obj[key] === 'object' && obj[key] !== null) {
                    obj[key] = undefinedToNull(obj[key]);
                }
                if (obj[key] === undefined) {
                    obj[key] = null;
                }
            }
        }
    }
  
    return obj;
}