Non-recursive traversal of a binary tree without a stack

Question

Non-recursive traversal of a binary tree without a stack

You need to build a non-recursive binary tree traversal algorithm that has the following properties:

A tree of n nodes is traversed in time O(n);
The amount of additional memory (except for the one allocated for the tree) does not exceed a certain constant;
During the execution of the algorithm, the tree cannot be modified even temporarily.

The only thing I could find on the topic is the Morris bypass, but this algorithm temporarily converts the tree is a "stitched" tree, so it doesn't fit.

2

алгоритм структуры-данных дерево бинарное-дерево

Author: DarkGenius, 2015-10-15

Source

1 answers

score 1 · Accepted Answer

If there is a reference to the parent , then you can take the algorithm from the answer How to do in-order traversal of a BST without recursion or stack but using parent pointers?

static void Walk(Node node)
{
    Node lastNode = null;
    while (node != null)
    {
        if (lastNode == node.Parent)
        {
            if (node.Left != null)
            {
                lastNode = node;
                node = node.Left;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Left)
        {
            Output(node);

            if (node.Right != null)
            {
                lastNode = node;
                node = node.Right;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Right)
        {
            lastNode = node;
            node = node.Parent;
        }
    }
}

But, strictly speaking, there is no reference to the parent in the BST, and it is impossible to bypass it without modifying the tree and with a memory limit.