Return to Answer

#include <cstdio>
#include <iostream>
#include <queue>

#define null NULL
#define int32 int

using namespace std;

/**
*   Binary tree node class
**/

template <class T>
class Node
{
    public:

    /*  Public Constructors */

        Node () :
            left (null),
            right (null),
            value ()
        {}

        explicit Node (T x) :
            left (null),
            right (null),
            value (x)
        {}

    /*  Public Attributes   */

        Node* left;
        Node* right;
        T value;

};

/**
*   This exception is thrown when the flattener & cycle detector algorithm encounters a cycle
**/

class CycleException
{

    public:

    /*  Public Constructors */

        CycleException () {}
        virtual ~CycleException () {}

};

/**
*   This functions flattens an alleged binary tree, throwing a new CycleException when encountering a cycle. Returns the root of the flattened binary tree.
**/

template <class T>
Node<T>* flatten (Node<T>* current)
{
    //  Count steps (well, kinda) to determine runtime
    int32 steps = 0;
    //  Keep track of the root node so the tree is not lost
    Node<T>* root = current;
    //  Keep track of the parent of the current node since it is needed for insertions
    Node<T>* parent = null;

    //  Loop while there are subtrees to process 
    while( current->left != null or current->right != null ){

        steps++;

        //  There is a left subtree, so current has a predecessor, which we will call "bottom" of the subtree
        if( current->left != null ){
            Node<T>* top = current->left;
            Node<T>* bottom;
            //  The top and the bottom is one and the same
            if( top->right == null ){
                bottom = top;
            }
            //  The bottom is buried in the right subtree of top
            if( top->right != null ){
                //  Find it using Floyd's cycle detection algorithm applied to right childs
                Node<T>* turtle = top;
                Node<T>* hare = top->right;
                while( hare->right != null ){
                    if( turtle == hare ){
                        throw new CycleException();
                    }
                    if( hare->right != null ){
                        steps++;
                        hare = hare->right;
                    }
                    if( hare->right != null ){
                        steps++;
                        hare = hare->right;
                    }
                    turtle = turtle->right;
                }
                bottom = hare;
            }
            //  Remove subtree from current
            current->left = null;
            //  Insert subtree between the current node and its parent, if there is any
            if( parent != null ){
                parent->right = top;
            }
            bottom->right = current;
            //  If the current node is the root then the top is the new root
            if( root == current ){
                root = top;
            }
            //  Step up to process the top, parent remains the same
            current = top;
            continue;
        }

        //  There is only a right subtree, Floyd's cycle detection algorithm must be applied to find a node that has a left subtree
        if( current->left == null and current->right != null ){
            cout << "Visited " << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
            Node<T>* hare = current->right;
            Node<T>* hareParent = current;
            Node<T>* turtle = current;
            while( hare->left == null and hare->right != null ){
                if( turtle == hare ){
                    throw new CycleException();
                }
                if( hare->left == null and hare->right != null ){
                    cout << "Visited " << dec << hare->value << " @ 0x" << hex << reinterpret_cast<int32>(hare) << endl;
                    steps++;
                    hare = hare->right;
                    hareParent = hareParent->right;
                }
                if( hare->left == null and hare->right != null ){
                    cout << "Visited " << dec << hare->value << " @ 0x" << hex << reinterpret_cast<int32>(hare) << endl;
                    steps++;
                    hare = hare->right;
                    hareParent = hareParent->right;
                }
                turtle = turtle->right;
            }
            current = hare;
            parent = hareParent;
            continue;
        }

    }

    cout << "Visited " << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
    cout << "Steps taken: " << dec << steps << endl;

    //  there are no more subtrees to process, we are finished, the tree does not contain cycles
    return root;

}

template <class T>
void traverseFlat (Node<T>* current)
{
    while( current != null ){
        cout << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
        current = current->right;
    }
}

template <class T>
Node<T>* makeCompleteBinaryTree (int32 maxNodes)
{
    Node<T>* root = new Node<T>();
    queue<Node<T>*> q;
    q.push(root);
    int32 nodes = 1;
    while( nodes < maxNodes ){
        Node<T>* node = q.front();
        q.pop();
        node->left = new Node<T>();
        q.push(node->left);
        nodes++;
        if( nodes < maxNodes ){
            node->right = new Node<T>();
            q.push(node->right);
            nodes++;
        }
    }
    return root;
}

template <class T>
void inorderLabel (Node<T>* root)
{
    int32 label = 0;
    inorderLabel(root, label);
}

template <class T>
void inorderLabel (Node<T>* root, int32& label)
{
    if( root == null ){
        return;
    }
    inorderLabel(root->left, label);
    root->value = label++;
    inorderLabel(root->right, label);
}


int32 main (int32 argc, char* argv[])
{
    if(argc||argv){}

    typedef Node<int32> Node;

    //  Make binary tree and label it in-order
    Node* root = makeCompleteBinaryTree<int32>(1 << 16);
    inorderLabel(root);

    //  Try to flatten it
    try{
        root = flatten(root);
    }catch(CycleException*){
        cout << "Oh noes, cycle detected!" << endl;
        return 0;
    }

    //  Traverse its flattened form
    traverseFlat(root);

}

#include <cstdio>
#include <iostream>
#include <queue>

#define null NULL
#define int32 int

using namespace std;

/**
*   Binary tree node class
**/

template <class T>
class Node
{

    public:

    /*  Public Attributes   */

        Node* left;
        Node* right;
        T value;

};

/**
*   This exception is thrown when the flattener & cycle detector algorithm encounters a cycle
**/

class CycleException
{

    public:

    /*  Public Constructors */

        CycleException () {}
        virtual ~CycleException () {}

};

/**
*   Biny tree flattener and cycle detector class.
**/

template <class T>
class Flattener
{

    public:

    /*  Public Constructors */

        Flattener () :
            root (null), 
            parent (null), 
            current (null),
            top (null),
            bottom (null),
            turtle (null),
        {}

        virtual ~Flattener () {}

    /*  Public Methods  */

        /**
        *   This function flattens an alleged binary tree, throwing a new CycleException when encountering a cycle. Returns the root of the flattened tree.
        **/

        Node<T>* flatten (Node<T>* pRoot)
        {
            init(pRoot);
            //  Loop while there are left subtrees to process
            while( findNodeWithLeftSubtree() ){
                //  We need to find the topmost and rightmost node of the subtree
                findSubtree();
                //  Move the entire subtree above the current node
                moveSubtree();
            }
            //  There are no more left subtrees to process, we are finished, the tree does not contain cycles
            return root;
        }

    protected:

    /*  Protected Methods   */ 

        void init (Node<T>* pRoot)
        {
            //  Keep track of the root node so the tree is not lost
            root = pRoot;
            //  Keep track of the parent of the current node since it is needed for insertions
            parent = null;
            //  Keep track of the current node, obviously it is needed
            current = root;
        }

        bool findNodeWithLeftSubtree ()
        {
            //  Find a node with a left subtree using Floyd's cycle detection algorithm
            turtle = parent;
            while( current->left == null and current->right != null ){
                if( current == turtle ){
                    throw new CycleException();
                }
                parent = current;
                current = current->right;
                if( current->right != null ){
                    parent = current;
                    current = current->right;
                }
                if( turtle != null ){
                    turtle = turtle->right;
                }else{
                    turtle = root;
                }
            }
            return current->left != null;
        }

        void findSubtree ()
        {
            //  Find the topmost node
            top = current->left;
            //  The topmost and rightmost nodes are the same
            if( top->right == null ){
                bottom = top;
                return;
            }
            //  The rightmost node is buried in the right subtree of topmost node. Find it using Floyd's cycle detection algorithm applied to right childs.
            bottom = top->right;
            turtle = top;
            while( bottom->right != null ){
                if( bottom == turtle ){
                    throw new CycleException();
                }
                bottom = bottom->right;
                if( bottom->right != null ){
                    bottom = bottom->right;
                }
                turtle = turtle->right;
            }
        }

        void moveSubtree ()
        {
            //  Update root; if the current node is the root then the top is the new root
            if( root == current ){
                root = top;
            }
            //  Add subtree below parent
            if( parent != null ){
                parent->right = top;
            }
            //  Add current below subtree
            bottom->right = current;
            //  Remove subtree from current
            current->left = null;
            //  Update current; step up to process the top
            current = top;
        }

        Node<T>* root;
        Node<T>* parent;
        Node<T>* current;
        Node<T>* top;
        Node<T>* bottom;
        Node<T>* turtle;

    private:

        Flattener (Flattener&);
        Flattener& operator = (Flattener&);

};

template <class T>
void traverseFlat (Node<T>* current)
{
    while( current != null ){
        cout << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
        current = current->right;
    }
}

template <class T>
Node<T>* makeCompleteBinaryTree (int32 maxNodes)
{
    Node<T>* root = new Node<T>();
    queue<Node<T>*> q;
    q.push(root);
    int32 nodes = 1;
    while( nodes < maxNodes ){
        Node<T>* node = q.front();
        q.pop();
        node->left = new Node<T>();
        q.push(node->left);
        nodes++;
        if( nodes < maxNodes ){
            node->right = new Node<T>();
            q.push(node->right);
            nodes++;
        }
    }
    return root;
}

template <class T>
void inorderLabel (Node<T>* root)
{
    int32 label = 0;
    inorderLabel(root, label);
}

template <class T>
void inorderLabel (Node<T>* root, int32& label)
{
    if( root == null ){
        return;
    }
    inorderLabel(root->left, label);
    root->value = label++;
    inorderLabel(root->right, label);
}


int32 main (int32 argc, char* argv[])
{
    if(argc||argv){}

    typedef Node<int32> Node;

    //  Make binary tree and label it in-order
    Node* root = makeCompleteBinaryTree<int32>(1 << 24);
    inorderLabel(root);

    //  Try to flatten it
    try{
        Flattener<int32> F;
        root = F.flatten(root);
    }catch(CycleException*){
        cout << "Oh noes, cycle detected!" << endl;
        return 0;
    }

    //  Traverse its flattened form
//  traverseFlat(root);

}

It uses O(1) space and it runs in O(n) for complete binary trees, and I am almost certain it runs in linear time for all inputs but haven't tested it thoroughly yet. It flattens the tree in the process, every node has the inorder successor in its right child, and null in the left. Cycle detection, tree flattening and in-order traversal in one piece!

The algorithm tries to flatten the binary tree by searching for the predecessor of the current node, and moving THE WHOLE LEFT SUBTREE above the current node. It preserves the in-order sequence of the tree. If there is no left subtree, it moves on to process the right subtree.

Let's call the left child of the current node the "top" and the predecessor of the current node the "bottom". If we know both, we can move the entire left subtree of the current node in a few operations. We move it above the current node so the tree will be more like a flattened tree (trading 1 left-child-relation to 1 right-child-relation in the process, you can verify that easily)

There are three main cases: bottom is top, bottom is in the right subtree of top, no left subtree.

The first case is the easiest, if bottom is top then all we need is a simple right rotation operation.

If bottom is in the right subtree of top, we need to find it first by going through all right childs with Floyd's cycle detection algorithm.

If there is no left subtree, we need to go through the right childs with Floyd's cycle detection algorithm to find a left subtree.

These are the only two cases where we can encounter a cycle. And obviously if there are no left or right subtrees we are finished.

Draw some graphs of all cases, it is really easy.

I suspect it doesn't go through an edge more than twice, but I do not have formal proof yet.

• Runtime: O(n). I suspect it goes through an edge at most a constant number of times. No formal proof.
• Space: O(1). Only stores a few nodes. Does not create new nodes or edges, only rearranges them.
• Destructive: Yes. It flattens the tree, every node has the inorder successor as its right child, and null as the left.

The algorithm tries to flatten the binary tree by moving the whole left subtree of the current node to above it, making it the rightmost node of the subtree, then updating the current node to find further left subtrees in the newly discovered nodes. If we know both the left child and the predecessor of the current node, we can move the entire subtree in a few operations, in a similar manner to inserting a list into another. Such a move preserves the in-order sequence of the tree and it invariably makes the tree more right slanted.

There are three cases depending on the local configuration of nodes around the current one: left child is the same as the predecessor, left child is different from the predecessor, or no left subtree. The first case is trivial. The second case requires finding the predecessor, the third case requires finding a node on the right with a left subtree. Graphical representation helps in understanding them.

In the latter two cases we can run into cycles. Since we only traverse a list of the right childs, we can use Floyd's cycle detection algorithm to find and report loops. Sooner or later every cycle will be rotated into such a form.

There are no cases where we can encounter a cycle. And obviously if there are no left or right subtrees we are finished.

These are the only two cases where we can encounter a cycle. And obviously if there are no left or right subtrees we are finished.