Выполните обход дерева по порядку (снизу вверх), взяв посещенные узлы и вставив их в BST.
Исключает ли "без лишних пробелов" рекурсию?
Если нет, то что-то вроде:
# top level call passes null for bst
bt_to_bst (root, bst)
# nothing to add to bst; just return it
if null(root) -> return bst
# if this is a leaf node, stick it into the BST
if null(root->left) && null(root->right)
return bst_insert(bst, root)
# otherwise add all of left subtree into the bst and then the right tree
bst = bt_to_bst (root->left, bst);
return bt_to_bst (root->right, bst);
bt_to_bst
- операция фильтрации; он берет существующий bst и возвращает новый с добавленным в него узлом.
Добавление листового узла в bst
безопасно, потому что мы никогда не посетим его снова, поэтому мы можем перезаписать его left
и right
указатели.