Всё дерево требует O(N) обхода: необходимо проверить каждый узел. При фиксированном наборе из двух имён допустимость одного ключа проверяется двумя сравнениями за O(1), но это не сокращает общий обход.
Как проверить ключи и вложенные узлы JSON-дерева?
Всё дерево требует O(N) обхода: необходимо проверить каждый узел. При фиксированном наборе из двух имён допустимость одного ключа проверяется двумя сравнениями за O(1), но это не сокращает общий обход.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Внешний JSON должен иметь форму {id:string, children?: Node[]}. Другие ключи запрещены на каждом узле. Вход получен JSON.parse, поэтому нет циклов, getters и символов. Можно ли проверить всё дерево за O(1), и как проверять допустимость одного имени ключа?
Ответ
Всё дерево требует O(N) обхода: необходимо проверить каждый узел. При фиксированном наборе из двух имён допустимость одного ключа проверяется двумя сравнениями за O(1), но это не сокращает общий обход.
Для узла проверьте object, не null и не массив, наличие собственного строкового id, отсутствие ключей кроме id/children. Если children присутствует, он должен быть массивом, каждый элемент которого проходит те же проверки. Используйте явный стек для глубокой вложенности и ограничение размера входа. Проверять только корень недостаточно: лишнее поле или неверный id могут находиться в любом потомке.