It expands the best let until memory is full. When there is no memory left to add newly generated node, it needs to drop one off the early expanded node. SMA* always drops the leaf node with highest f -cost. The dropped node is called “forgotten node”.

SMAthen backs up the value of the forgotten node to its parent. In this way, the quality of the best path in that sub-tree is always known to the ancestor of a forgotten sub tree. This information is used when all other paths look worse than the path it has forgotten. In that case SMA regenerates the forgotten sub-tree.

If all nodes have same f value, then to avoid selecting the same node deletion and expansion, SMA*expands the “newest best” leaf and deletes the “oldest worst” leaf.

If there is only one leaf, even these coincide, but in that case, the current search tree must be a single path from root node to leaf that fills all of memory. If leaf is not is a goal node, even if it is on optimal solution path, that solution is not reachable with the available memory.