Converting a multiway tree to left-child/right-sibling format?

Question

I'm trying to write C++ code that, given a multiway tree, converts that tree into a binary tree represented in the left-child/right-sibling format. For example, given this tree:

          A
        / | \
       B  C  D
     / | \   |
    E  F  G  H
      / \
     I   J

I'd like to output this tree:

I'm not sure how to approach this problem. How should I think about doing this?

You will find some helpful information [at this link](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). Just read the information at the link, practice, and you'll be able to write your code in no time at all! — Sam Varshavchik, Dec 15 '18 at 20:52
Welcome to Stack Overflow! Can you elaborate on how you're trying to convert the tree into a binary tree? Are you looking for something like the left-child/right-sibling representation? Also, can you more generally talk us through what you've tried so far? We're happy to help out, but without knowing what you've attempted it's hard to do that. — templatetypedef, Dec 15 '18 at 20:55
@Amna Alnajjar: Do you already have a c++ type or class declaration for the general tree and/or binary tree? — Jörg Brüggmann, Dec 15 '18 at 20:58
@Amna Alnajjar: If not, what exactly do you mean by general tree? — Jörg Brüggmann, Dec 15 '18 at 20:59
@templatetypedef yes I am trying to convert the tree to a left child - right sibling representation — Amna Alnajjar, Dec 15 '18 at 21:00
@Jörg'Wuwei'Brüggmann by general tree I mean that each node can have multiple nodes connected to it and all connected nodes are the children of this node. I want to convert it this tree to left-child/right-sibling representation. — Amna Alnajjar, Dec 15 '18 at 21:09
There is no universal algorithm for making this kind of a transformation on an arbitrary tree. You will have to figure out the algorithm you need to use by yourself, nobody on stackoverflow.com will do it for you; and then implement it in C++. — Sam Varshavchik, Dec 15 '18 at 21:25

score 2 · Answer 1 · answered Dec 15 '18 at 21:26

There's a nice recursive insight you can use for solving this problem. I'll let you work out the details about how to actually implement this in code, since I don't know how you have the tree represented, but here's the core idea.

First, it's really easy to convert an empty tree into LC/RS format: it comes back as the empty tree.

On the other hand, suppose you have a nonempty tree. Start off by converting each of its children into LC/RS format (recursively). For example, given this tree:

          A
        / | \
       B  C  D
     / | \   |
    E  F  G  H
      / \
     I   J

You'd start off by recursively converting each child to LC/RS, giving back these three trees:

   B        C         D
  /                  /
 E                  H
  \
   F
  / \
 I   G
  \
   J

These trees currently are free-floating and not linked to one another. But since you know that they're siblings, you'll want to make C the right child of B and D the right child of C. That's essentially a linked list traversal. Here's what things should look like when you're done:

Once you've done that, all that's left to do is make B the left child of A, as shown here:

To recap, the logic goes like this:

If the tree to convert is empty, return an empty tree.
Otherwise:
- Recursively convert each of the children of the root node into LC/RS format.
- Iterate across those trees, assigning right child links to link the trees together.
- Assign A's left child pointer to point to the resulting tree (or to null if it has no children).

I'll leave the C++ details to you to fill in. If you've made an attempt to solve this problem and are running into trouble, feel free to post a follow-up question detailing the code that you've written so far along with a specific test case that's failing or the specific compiler errors you're encountering. Good luck!

Jörg Brüggmann · Answer 2 · 2018-12-16T15:53:52.480

Presuming

Assuming a binary tree is meant according to https://en.wikipedia.org/wiki/Binary_tree and the multi-way tree is like a binary tree but with countable subnodes instead of optional left and right subnodes, whereas the algorithm is according to https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree.

Types

The types may be the following templates - for the multi-way tree:

template <typename T>
class CMultiWayTree {
public:
    typedef CMultiWayTree<T>*   NodePtr;
    typedef list<NodePtr>       List;
public:
    T                           m_tData;
protected:
    List                        m_lNodes;
public:
    // ...
};

...and for the binary tree:

template <typename T>
class CBinaryTree {
public:
    typedef CBinaryTree<T>*     NodePtr;
public:
    typedef CGeneralTree<T>*    MTNodePtr;
public:
    T                           m_tData;
protected:
    NodePtr                     m_pLeftNode;
    NodePtr                     m_pRightNode;
    //...
};

Code

If assuming right, then the code may be like below. Whereas the conversion algorithm ("Left-child right-sibling binary tree") is implemented in constructor "CBinaryTree(MTNodePtr pmtToConvert)".

#include    <iostream>
#include    <list>

using namespace std;

string  ident(int nDepth) {
    string  sIndent;

    for (int n = 0; n < nDepth; n++) {
        sIndent += ' ';
    }
    return sIndent;
}

template <typename T>
class CMultiWayTree {
public:
    typedef CMultiWayTree<T>*   NodePtr;
    typedef list<NodePtr>       List;
public:
    T                           m_tData;
protected:
    List                        m_lNodes;
public:
    CMultiWayTree(const T& rtData) {
        m_tData = rtData;
    };
    virtual ~CMultiWayTree() {
        typename List::iterator it;

        it = m_lNodes.begin();
        while ( it != m_lNodes.end() ) {
            delete (*it);
            it++;
        }
    }
    virtual const T& getNode() { 
        return m_tData;
    };
    virtual void goToFirstChildNode(typename List::iterator& it) { 
        it = m_lNodes.begin();
    };
    virtual void goToNextChildNode(typename List::iterator& it) { 
        it++;
    };
    virtual bool getChildNode(typename List::iterator& it, NodePtr& pNode) { 
        bool    bIsChildNode;

        bIsChildNode = it != (m_lNodes.end());
        if ( bIsChildNode ) {
            pNode = (*it);
        } else {
            pNode = NULL;
        }
        return bIsChildNode;
    };
    virtual NodePtr appendChildNode(const T& rtData) { 
        NodePtr pNode = new CMultiWayTree(rtData);
        m_lNodes.push_back(pNode);
        return pNode;
    };
    virtual void print(ostream& os, int nDepth = 0) { 
        NodePtr     pNode;
        typename List::iterator     it;

        os << ident(nDepth) << m_tData << endl;
        nDepth++;
        goToFirstChildNode(it);
        while ( getChildNode(it, pNode) ) {
            pNode->print(os, nDepth);
            goToNextChildNode(it);
        }
    };
};

template <typename T>
class CBinaryTree {
public:
    typedef CBinaryTree<T>*     NodePtr;
public:
    typedef CMultiWayTree<T>*   MTNodePtr;
public:
    T                           m_tData;
protected:
    NodePtr                     m_pLeftNode;
    NodePtr                     m_pRightNode;
public:
    CBinaryTree(const T& rtData) {
        m_tData = rtData;
        m_pLeftNode = NULL;
        m_pRightNode = NULL;
    };
    CBinaryTree(GTNodePtr pmtToConvert) {
        if ( pmtToConvert != NULL ) {
            NodePtr                                     pNewNode;
            MTNodePtr                                   pNode;
            typename CMultiWayTree<T>::List::iterator   it;

            m_tData = pmtToConvert->m_tData;

            m_pRightNode = NULL;
            pmtToConvert->goToFirstChildNode(it);
            if ( pmtToConvert->getChildNode(it, pNode) ) {
                pNewNode = new CBinaryTree(pNode);
                m_pLeftNode = pNewNode;
                pmtToConvert->goToNextChildNode(it);
            } else {
                m_pLeftNode = NULL;
            }
            while ( pmtToConvert->getChildNode(it, pNode) ) {
                pNewNode = pNewNode->setRight(new CBinaryTree(pNode));
                pmtToConvert->goToNextChildNode(it);
            }
        }
    };
    virtual ~CBinaryTree() {
        if ( m_pLeftNode != NULL ) {
            delete m_pLeftNode;
            m_pLeftNode = NULL;
        }
        if ( m_pRightNode != NULL ) {
            delete m_pRightNode;
            m_pRightNode = NULL;
        }
    };
    virtual NodePtr setRight(NodePtr pNew) {
        if ( m_pRightNode != NULL ) {
            delete m_pRightNode;
        }
        m_pRightNode = pNew;
        return m_pRightNode;
    }
    virtual void print(ostream& os, int nDepth = 0, char chPreFix = '\0') { 
        NodePtr     pNode;

        if ( chPreFix != '\0' ) {
            os << ident(nDepth - 1) << chPreFix << m_tData << endl;
        } else {
            os << ident(nDepth) << m_tData << endl;
        }
        nDepth++;
        if ( m_pRightNode != NULL ) {
            m_pRightNode->print(os, nDepth, 'r');
        }
        if ( m_pLeftNode != NULL ) {
            m_pLeftNode->print(os, nDepth, 'l');
        }
    };
};

int main() {
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNode = new CMultiWayTree<char>('A');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeB = pMultiWayTreeNode->appendChildNode('B');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeC = pMultiWayTreeNode->appendChildNode('C');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeD = pMultiWayTreeNode->appendChildNode('D');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeE = pMultiWayTreeNodeB->appendChildNode('E');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeF = pMultiWayTreeNodeB->appendChildNode('F');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeG = pMultiWayTreeNodeB->appendChildNode('G');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeH = pMultiWayTreeNodeD->appendChildNode('H');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeI = pMultiWayTreeNodeF->appendChildNode('I');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeJ = pMultiWayTreeNodeF->appendChildNode('J');

    cout << "Input (multi-way tree):" << endl;
    pMultiWayTreeNode->print(cout, 3);
    cout << endl;

    CBinaryTree<char>::NodePtr  pBinaryTreeNode = new CBinaryTree<char>(pMultiWayTreeNode);

    cout << "Output (binary tree):" << endl;
    pBinaryTreeNode->print(cout, 3);

    delete pMultiWayTreeNode;
    delete pBinaryTreeNode;

    return 0;
}

Output

The program will create the following output:

Input (multi-way tree):
   A
    B
     E
     F
      I
      J
     G
    C
    D
     H

Output (binary tree):
   A
   lB
    rC
     rD
      lH
    lE
     rF
      rG
      lI
       rJ

@Amna Alnajjar: Could we help you? – Jörg Brüggmann Dec 21 '18 at 10:18 — Jörg Brüggmann, Dec 21 '18 at 10:18

Converting a multiway tree to left-child/right-sibling format?

2 Answers2