Print Balanced Tree nodes using level order traversal from bottom up

I do not know what is the motivation for searching the solution. I also do not know what that kind of traversal is good for. I have never saw the need for that kind of traversal. Also the nodes do not seem to be orderded the way that is usual when using binary trees. You should possibly tell more details about the purpose.

Anyway, I think that your solution of the problem is almost optimal and I can see no way how to do it without some extra data structure. I even cannot see how that traversal would be done recursively (but I may be blind). The reasons are:

1. Whenever you traverse a binary tree, the only nodes that are available immediately (if they exist) are the left node and the right node.

2. Every traversal at least at some point jumps to a node that is other than described in point 1.

3. Every traversal needs a kind of jump-back-to-the-previously-processed-node or near to it. This way, the previous or near position must be remembered somehow. Or in the form of hidden stack when solving it recursively, or in the form of the application-level stack when removing recursion, or in some other form.

4. This traversal does not fit with the recursive definition of a binary tree (i.e. "Binary tree is empty or it has the root node with left and right subtrees."). The recursive traversals always process the node, the left tree and the right tree. Only the order of the three operations makes them different. Your traversal cannot be expressed this way. Because of that I believe it cannot be solved recursively.

Short summary: Any tree traversal needs extra memory -- or hidden when doing it recursively, or in explicitly defined data structures.

If the program can use C++ and not C only, I would only suggest one enhancement to your code -- using std::queue<mynode *> for implementing the queue.

Here is the sample that uses the mentioned std::queue. The good thing is that there is no restriction to number of levels (even though the balanced tree would not have too many levels). Also, I prefer explicit testing against NULL. But it is a matter of taste.

#include <queue>
#include <iostream>
 
using namespace std;
 
class mynode
{
public:
    mynode(int val, mynode * L, mynode * R)
    {
        value = val;
        left = L;
        right = R;
    }
 
    int value;
    mynode * left;
    mynode * right;
};
 
 
void levelOrderTraversal(mynode *root)
{
    queue<mynode *> q;
 
    while (root != NULL)
    {
        cout << "[" << root->value << "] ";
 
        if (root->left != NULL)
        {
            q.push(root->left);
        }
 
        if (root->right != NULL)
        {
            q.push(root->right);
        }
     
        if ( ! q.empty())
        {
            root = q.front();
            q.pop();
        }
        else
        {
            root = NULL;
        }    
    }
}
 
 
void deleteTree(mynode *root)
{
    if (root != NULL)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
}
 
 
int main ()
{
    // Building the tree.
    mynode * p5 = new mynode(5, NULL, NULL);
    mynode * p6 = new mynode(6, NULL, NULL);
    mynode * p7 = new mynode(7, NULL, NULL);
    mynode * p8 = new mynode(8, NULL, NULL);
 
    mynode * p2 = new mynode(2, p5, p6);
    mynode * p3 = new mynode(3, p7, p8);
 
    mynode * root = new mynode(1, p2, p3);
 
    // Do the traversal.
    levelOrderTraversal(root);
 
    // Delete the tree recursively.
    deleteTree(root);
 
    return 0;
}

Select allOpen in new window

If you add a pointer-to-parent and pointer-to-next-sibling to the nodes, you can easily do it without recursion or an extra container.
Just simply descend to the lowest level, and print that level using the pointer-to-next-sibling's, then go up to the previous level using the pointer-to-parent of the leftmost sibling.

This basically keeps a tree within the tree, where the bottom left node is the "root" ...

>>>> If you add a pointer-to-parent and pointer-to-next-sibling to the nodes

You can do it without these additional pointers:

For level traversion a binary tree can be displayed like

                      1
           2                          3
      4          5            6            7
  8      9   A     B     C    D     E       F

Using binary numbers instead of hex we get

 
                             0001
              0010                             0011
     0100          0101           0110         0111
1000 1001 1010 1011   1100 1101 1110 1111


Given an arbitrary position (number), e. g.  D == 1101, we can traverse to that position by checking the bits of that number. The most left '1' means that we were at level 3, the next '1' mean that we have to take the right child pointer from root (pos 3 == 0011) , the next '0' means, that we go left (pos 6 == 0110) and the last '1' means that we go right after that. Found. If any node on the way was NULL we break cause the branch doesn't exist then.  

The code for that would be like (I assumed you know the depth of the tree somehow)
 
for (l = depth; l >= 0; --l)
{
    for (k = 1<<l; k < (1<<(l+1)); k++)
    {  
        mynode* next = root;
        for (n = 1; n < l; ++n)
        {
            if (k & (1<<(l - n)))
            {
                 if (!next->right)
                 {
                     cout << "- ";
                     return;
                 }
                 next = next->right;
             }
             else
            {
                  // do the same for left side
                  ....
            }
        }
               
    }
     if (next != NULL)
          cout << next->data << " ";
     else
          // print empty node "- "
          ...
}


The most outer loop iterates all levels (reverse), the next loop iterates all positions within one level, the next loop iterates up to the current level, deciding whether to go left or right by checking the appropriate bit of the position (1-based) to look for. If there was no break, it finally found the node searched for.

Regards, Alex

Interesting idea, Alex. To make it work good, you can store the nodes in an array, with the binary position value as index.

>>>> To make it work good, you can store the nodes in an array
Yes, you would have a direct access to all nodes with that. However,  the requirements here were to not using an extra data structure and - beside of traversing - there is no real benefit when doing so, e. g. for seeking a value in the tree. Of course you could 'calculate' the 'approximate' position of a value by comparing with the min and max (the positions are 1<<(depth-1) and (1<<depth) -1, then correct the 'approximation' by comparing with the approximated node, and so on. But I fear that method is slower than a normal binary search ...

I have good experiences by using a sorted array instead of a binary tree. The binary search is as fast as in a binary tree and in case of 'growing' keys, e. g. date-based keys or id numbers, you mostly will insert at end of the array so that the costs for inserting were comparable with that of a binary tree.

>> However,  the requirements here were to not using an extra data structure and - beside of traversing - there is no real benefit when doing so, e. g. for seeking a value in the tree.

What I meant was to store the nodes in an array, indexed on your position value, but still keep the normal left and right child node pointers.

So, this example tree :

          1
     2        3

would look like :

        --------
    ---|   1   |---
    |   --------   |
    ->|   2   |   |
        --------   |
        |   3   |<-
        --------

etc. Keeping the tree balanced when inserting or removing nodes becomes a harder task though, but looking up nodes and printing in the required order becomes easier.

Infinity08> If you add a pointer-to-parent and pointer-to-next-sibling to the nodes, you can easily do it without recursion or an extra container.

Yes. But the extra pointer is a kind of distributed extra data structure. The main problem is how difficult it would be to fill the extra pointer. Insertion can be very costly. Also ballancing the tree (if required) means updating the extra pointers.  It works with what I have heard named "monkey-puzzle tree" where the extra pointer reflects the in-order traversal. However, it would be costly operation in the above case.

I agree, pepr, insertion and deletion will indeed be more costly ... but at the moment you want to look for a node, or print all nodes, there will be no performance impact, and no need to create an extra data structure.

A lot depends on the ratio of lookups versus inserts/deletes. If that ratio is sufficiently high, then the method I described is a good alternative.

>>>> The main problem is how difficult it would be to fill the extra pointer.
>>>> Insertion can be very costly.
I have a tree with that spec. It is not a binary tree as each node can have an arbitrary count of siblings. The management of the extra pointers is a minor thing compared to the advantages regarding traversing and balancing.

The tree was used as a baseclass for a FileTree wiith (nested) folders and files.

Regards, Alex

#ifndef TREE_HPP
#define TREE_HPP
 
// project includes
 
// basis types and macros
#ifndef BASTYPES_HPP
   #include <bastypes.hpp>
#endif
 
// handle concurrency in a multithreading environment
#ifndef MUTEX_HPP
   #include <mutex.hpp>
#endif
 
// dynamic array collecion
#ifndef HAT_HPP
    #include <hat.hpp>
#endif
 
// string class 
#ifndef STRING_HPP
    #include <string.hpp>
#endif
 
// forward declaration
 
template <class TNodeData, class TLeafData>
class Tree;
 
template <class TNodeData, class TLeafData>
class TreeIterator;
 
template <class TNodeData, class TLeafData>
class TreeNode;
 
template <class TNodeData, class TLeafData>
class TreeLeaf;
 
// macros for easier template type declaration
 
#define TreeItemPtr                 TreeItem*
#define TreeNodePtr                 TreeNode<TNodeData, TLeafData>*
#define TreeLeafPtr                 TreeLeaf<TNodeData, TLeafData>*
#define TreePtr                     Tree<TNodeData, TLeafData>*
#define TreeRef                     Tree<TNodeData, TLeafData>&
#define TreeIteratorPtr             TreeIterator<TNodeData, TLeafData>*
#define TreeIteratorRef             TreeIterator<TNodeData, TLeafData>&
 
// default macros
#ifndef DEFAULT_PATH_SEPARATOR
    #define DEFAULT_PATH_SEPARATOR      '/'
#endif
 
// macros for easier code reading
#define HANDLE_CHAIN_TRUE           True
#define HANDLE_CHAIN_FALSE          False
#define IS_TREE_OWNER_TRUE          True
#define IS_TREE_OWNER_FALSE         False
#define IS_DATA_OWNER_TRUE          True
#define IS_DATA_OWNER_FALSE         False
#define LOOK_IN_SUB_TRUE            True
#define LOOK_IN_SUB_FALSE           False
#define GOTO_NEXT_LEAF_TRUE         True
#define GOTO_NEXT_LEAF_FALSE        False
#define START_ITERATION_TRUE        True
#define START_ITERATION_FALSE       False
#define INCLUDE_LEAFS_FALSE         False
#define INCLUDE_LEAFS_TRUE          True
#define FORWARD_TRUE                True
 
/////////////////////////////////////////////////////////////////////////////
// @doc   Tree
//
 
 
// @class Base class for elements of a tree. A TreeItem holds pointers to the parent, previous and next tree element 
//
 
class TreeItem
{
// @dataprivate
private:
    // Attributes
    String               m_key;         // @cmember item key (should be unique for all siblings)
    TreeItemPtr          m_pParent;     // @cmember pointer to parent node item or NULL if root
    TreeItemPtr          m_pPrev;       // @cmember pointer to previous item of the same level or NULL if first
    TreeItemPtr          m_pNext;       // @cmember pointer to next item of the same level or NULL if last
 
// @funcpublic
public:
    // constructors, destructor
 
    // @cmember constructor for any item, node or leaf; 
    TreeItem(const String& key, TreeItemPtr pParent=NULL, TreeItemPtr pPrev=NULL, TreeItemPtr pNext=NULL);
    // @cmember destructor makes nothing; data must be deleted before destructing (by tree)
    virtual ~TreeItem();
 
public:
    // @cmember get key
    String                      getKey()
        { return m_key; }
 
protected:
    // @cmember get parent node 
    TreeItemPtr                 getParent()
        { return m_pParent; }
    // @cmember get previous child 
    TreeItemPtr                 getPrev()
        { return m_pPrev; }
    // @cmember get next child 
    TreeItemPtr                 getNext()
        { return m_pNext; }
    // @cmember get path
    String                      getPath(Char cPathSeparator);
    // @cmember set new parent node and return old one
    TreeItemPtr                 setParent(TreeItemPtr pParent)
        { TreeItemPtr pOld = m_pParent; m_pParent = pParent; return pOld; }
    // @cmember set new backward pointer for level chain and return old one
    TreeItemPtr                 setPrev(TreeItemPtr pPrev, Bool handleChain = True)
        { TreeItemPtr pOld = m_pPrev; m_pPrev = pPrev; 
          if (handleChain) 
          { if (pOld != NULL)  { pOld->m_pNext = pPrev; } 
            if (pPrev != NULL) { pPrev->m_pPrev = pOld; pPrev->m_pNext = this; }
          }
          return pOld; 
        }
    // @cmember set new forward pointer for level chain and return old one
    TreeItemPtr                 setNext(TreeItemPtr pNext, Bool handleChain = True)
        { TreeItemPtr pOld = m_pNext; m_pNext = pNext; 
          if (handleChain) 
          { if (pOld != NULL)  { pOld->m_pPrev = pNext; }
            if (pNext != NULL) { pNext->m_pNext = pOld; pNext->m_pPrev = this; }  
          }
          return pOld; 
        }
    // @cmember remove from same level chain
    Void                        chainOut()
        {   if (m_pPrev != NULL) { m_pPrev->m_pNext = m_pNext; }  // chain left sibling (if any) to right one
            if (m_pNext != NULL) { m_pNext->m_pPrev = m_pPrev; }  // chain right sibling (if any) to left one
        }
    // @cmember set new key
    String                      setKey(const String& key)
        { String oldKey = m_key; m_key = key; return oldKey; }
 
};
 
/////////////////////////////////////////////////////////////////////////////
// @doc   TreeNode
//
// @class  Derived class of class TreeItem to hold nodes. A node is a tree item  
//   <nl>  that may be parent of a list of leafs and/or parent of a list of
//         child nodes, Nodes and leafs may associate different data types
//
 
template <class TNodeData, class TLeafData>
class TreeNode  : public TreeItem
{
// @dataprivate
private:
    // Attributes
    TNodeData*           m_pData;        // @cmember pointer to data
    TreeNodePtr          m_pFirstKid;    // @cmember pointer to first child node or NULL if last level
    TreeNodePtr          m_pLastKid;     // @cmember pointer to last child node or NULL if last level
    TreeLeafPtr          m_pFirstLeaf;   // @cmember pointer to first leaf or NULL if no leafs
    TreeLeafPtr          m_pLastLeaf;    // @cmember pointer to last leaf or NULL if no leafs
 
// @funcpublic
public:
    // constructors, destructor
 
    // @cmember constructor for node; gets node data, parent and left and right sibling
    TreeNode(const String& nodeName,  TreeNodePtr pParent=NULL,
             TreeNodePtr pPrev=NULL,  TreeNodePtr pNext=NULL,   TNodeData* pNodeData=NULL
             );
    // @cmember destructor deletes the array (chain) but not the data
    virtual ~TreeNode();
 
private:
    // @cmember delete data if a tree item owns its data; the ownership property is 
    //          a property of the whole tree rather than of a single tree item
    Void                        deleteData();
 
public:
    // @cmember get data pointer
    TNodeData*                  getData()
        { return m_pData; }
    // @cmember get parent node 
    TreeNodePtr                 getParent()
        { return (TreeNodePtr)TreeItem::getParent(); }
    // @cmember get previous child 
    TreeNodePtr                 getPrev()
        { return (TreeNodePtr)TreeItem::getPrev(); }
    // @cmember get next child 
    TreeNodePtr                 getNext()
        { return (TreeNodePtr)TreeItem::getNext(); }
    // @cmember get first child 
    TreeNodePtr                 getFirstKid()
        { return m_pFirstKid; }
    // @cmember get last child 
    TreeNodePtr                 getLastKid()
        { return m_pLastKid; }
    // @cmember get first leaf 
    TreeLeafPtr                 getFirstLeaf()
        { return m_pFirstLeaf; }
    // @cmember get last leaf 
    TreeLeafPtr                 getLastLeaf()
        { return m_pLastLeaf; }
    // @cmember check for next level 
    Bool                        hasKids()
        { return m_pLastKid != NULL; }
    // @cmember check for leafs 
    Bool                        hasLeafs()
        { return m_pLastLeaf != NULL; }
 
    // @cmember set new data pointer and return olds one
    TNodeData*                  setData(TNodeData* pData)
        { TNodeData* pOld = m_pData; m_pData = pData; return pOld; }
    // @cmember set new parent pointer for level chain and return old one
    TreeNodePtr                 setParent(TreeNodePtr pParent)
        { return (TreeNodePtr)TreeItem::setParent(pParent); }
    // @cmember set new backward pointer for level chain and return old one
    TreeNodePtr                 setPrev(TreeNodePtr pPrev, Bool handleChain = True)
        { TreeNodePtr pOld = (TreeNodePtr)TreeItem::setPrev(pPrev, handleChain); 
          if (handleChain)
          {  TreeNodePtr pPar = getParent();
             if (pOld == NULL && pPar != NULL) { pPar->m_pFirstKid = pPrev; }
          }
          return pOld;
        }
    // @cmember set new forward pointer for level chain and return old one
    TreeNodePtr                 setNext(TreeNodePtr pNext, Bool handleChain = True)
        { TreeNodePtr pOld = (TreeNodePtr)TreeItem::setNext(pNext, handleChain);
          if (handleChain)
          { TreeNodePtr pPar = getParent();
            if (pOld == NULL && pPar != NULL) { pPar->m_pLastKid = pNext; }
          }
          return pOld;
        }
    // @cmember remove from same level chain
    Void                        chainOut()
    { TreeNodePtr pParent = getParent();
      if (pParent != NULL) 
      { if (pParent->m_pFirstKid == this) { pParent->m_pFirstKid = getNext(); }
        if (pParent->m_pLastKid == this)  { pParent->m_pLastKid  = getPrev(); } 
      }
      TreeItem::chainOut();
    }
    // @cmember set new start pointer for level chain and return old one
    TreeNodePtr                 setFirstKid(TreeNodePtr pFirstKid)
        { TreeNodePtr pOld = m_pFirstKid; m_pFirstKid = pFirstKid; return pOld; }
    // @cmember set new last pointer for level chain and return old one
    TreeNodePtr                 setLastKid(TreeNodePtr pLastKid)
        { TreeNodePtr pOld = m_pLastKid; m_pLastKid = pLastKid; return pOld; }
    // @cmember set new start pointer for leaf chain and return old one
    TreeLeafPtr                 setFirstLeaf(TreeLeafPtr pFirstLeaf)
        { TreeLeafPtr pOld = m_pFirstLeaf; m_pFirstLeaf = pFirstLeaf; return pOld; }
    // @cmember set new last pointer for leaf chain and return old one
    TreeLeafPtr                 setLastLeaf(TreeLeafPtr pLastLeaf)
        { TreeLeafPtr pOld = m_pLastLeaf; m_pLastLeaf = pLastLeaf; return pOld; }
 
    friend class TreeLeaf<TNodeData, TLeafData>;
    friend class Tree<TNodeData, TLeafData>;
};
 
/////////////////////////////////////////////////////////////////////////////
// @doc   TreeLeaf
//
// @class  Derived class of class TreeItem to hold leafs. A leaf is a child   
//   <nl>  tree item that has no child items
 
template <class TNodeData, class TLeafData>
class TreeLeaf  : public TreeItem
{
// @dataprivate
private:
    // Attributes
    TLeafData*                  m_pData;       // @cmember pointer to data
 
// @funcpublic
public:
    // constructors, destructor
 
    // @cmember constructor for node; gets all linked tree items
    TreeLeaf(const String& leafName, TreeNodePtr pParent, TreeLeafPtr pPrev=NULL, TreeLeafPtr pNext=NULL, TLeafData* pLeafData=NULL );
    // @cmember destructor deletes the array (chain) but not the data
    virtual ~TreeLeaf();
 
private:
    // @cmember delete data if a tree item owns its data; the ownership property is 
    //          a property of the whole tree rather than of a single tree item
    Void                        deleteData();
 
public:
    // @cmember get data pointer
    TLeafData*                  getData()
        { return m_pData; }
    // @cmember get parent node 
    TreeNodePtr                 getParent()
    { return (TreeNodePtr)TreeItem::getParent(); }
    // @cmember get previous child 
    TreeLeafPtr                 getPrev()
        { return (TreeLeafPtr)TreeItem::getPrev(); }
    // @cmember get next child 
    TreeLeafPtr                 getNext()
        { return (TreeLeafPtr)TreeItem::getNext(); }
    // @cmember set new data pointer and return olds one
    TLeafData*                  setData(TLeafData* pData)
        { TLeafData* pOld = m_pData; m_pData = pData; return pOld; }
    // @cmember set new parent pointer for level chain and return old one
    TreeNodePtr                 setParent(TreeNodePtr pParent)
        { return (TreeNodePtr)TreeItem::setParent(pParent); }
    // @cmember set new backward pointer for level chain and return old one
    TreeLeafPtr                 setPrev(TreeLeafPtr pPrev, Bool handleChain = True)
        { TreeLeafPtr pOld = (TreeLeafPtr)TreeItem::setPrev(pPrev, handleChain);
          if (handleChain)
          { TreeNodePtr pPar = getParent();
            if (pOld == NULL && pPar != NULL) { pPar->m_pFirstLeaf = pPrev; }
          }
          return pOld;
        }
    // @cmember set new forward pointer for level chain and return old one
    TreeLeafPtr                 setNext(TreeLeafPtr pNext, Bool handleChain = True)
        { TreeLeafPtr pOld = (TreeLeafPtr)TreeItem::setNext(pNext, handleChain);
          if (handleChain)
          { TreeNodePtr pPar = getParent();
            if (pOld == NULL && pPar != NULL) { pPar->m_pLastLeaf = pNext; }
          }
          return pOld;
        }
    // @cmember remove from same level chain
    Void                        chainOut()
    { TreeNodePtr pParent = getParent();
      if (pParent->m_pFirstLeaf == this) { pParent->m_pFirstLeaf = getNext(); }
      if (pParent->m_pLastLeaf == this)  { pParent->m_pLastLeaf  = getPrev(); } 
      TreeItem::chainOut();
    }
 
    friend class TreeNode<TNodeData, TLeafData>;
    friend class Tree<TNodeData, TLeafData>;
};
 
/////////////////////////////////////////////////////////////////////////////
// @class  Tree
//   <nl>  Collection class to handle a tree with nodes and leafs where any  
//   <nl>  node may be (unique) parent of a list of nodes and/or a list of leafs,
//   <nl>  e.g. the directory and file tree of a hierarchical file system 
 
template <class TNodeData, class TLeafData>
class Tree
{
// @dataprivate
private:
    // Attributes
 
    // @cmember pointer of the root node
    TreeNodePtr             m_pRoot;
    // @cmember indicates that the tree is owner of all its tree items, thus is responsible for deletion
    Bool                    m_isTreeOwner;  
    // @cmember indicates that any tree item deletes its data when destructed
    Bool                    m_isDataOwner;  
    // @cmember list of iterators currently operating on this tree
    Hat<TreeIteratorPtr>    m_iteratorList;
 
// @funcpublic
public:
    // constructors, destructor
 
    // @cmember constructor for tree; gets root data 
    Tree(const String& rootName, TNodeData* pRootData=NULL, Bool isTreeOwner=True, Bool isDataOwner=True);
 
private:
    // @cmember constructor for tree; gets root data pointer
    Tree(TreeNodePtr pRoot);
 
public:
    // @cmember destructor deletes items and data depending on ownership
    virtual ~Tree();
 
public:
    // @cmember get root data 
    TNodeData*                  getRootData()
        { return (m_pRoot == NULL)? NULL : m_pRoot->getData(); }
    // @cmember check if data owner
    Bool                        isDataOwner()
        {   return m_isDataOwner; }
    // @cmember check if tree owner
    Bool                        isTreeOwner()
        {   return m_isTreeOwner; }
    // @cmember check if tree is empty ( having no nodes or only the root node)
    Bool                        isEmpty()
        {   return ( m_pRoot == NULL || ( !( m_pRoot->hasKids() && ! m_pRoot->hasLeafs() ) ) ); }
 
private:
    // @cmember get root node 
    TreeNodePtr                 getRoot()
        { return m_pRoot; }
    // @cmember set root node  
    TreeNodePtr                 setRoot(TreeNodePtr pRoot, Bool isTreeOwner=True, Bool isDataOwner=True);
    // @cmember add new iterator to iterator list
    int                         registerIterator(TreeIteratorPtr pIterator)
        {  int idx = m_iteratorList.index(pIterator); return (idx >= 0)? idx : m_iteratorList.append(pIterator); } 
    // @cmember remove iterator from iterator list
    int                         unregisterIterator(TreeIteratorPtr pIterator)
        {  int idx = m_iteratorList.index(pIterator); if (idx >= 0 ) { m_iteratorList.removeAt(idx); } return idx; } 
    // @cmember notify any concurrent iterator when a node or leaf was deleted
    Bool                        notifyDeletion(TreeIteratorPtr pIterator, TreeNodePtr pItemDeleted);
    // @cmember notify any concurrent iterator when a leaf was deleted
    Bool                        notifyDeletion(TreeIteratorPtr pIterator, TreeLeafPtr pItemDeleted);
    // @cmember get any concurrent iterator to notify when a node or leaf was deleted 
    TreeIteratorPtr             getNextConcurrentIterator(TreeIteratorPtr pInitiator, int& nextIndex);
 
    friend class TreeIterator<TNodeData, TLeafData>;
};
 
 
/////////////////////////////////////////////////////////////////////////////
// @class  TreeIterator
//   <nl>  Operates on a tree with nodes and leafs where any  
//   <nl>  node may be (unique) parent of a list of nodes and/or a list of leafs,
//   <nl>  e.g. the directory and file tree of a hierarchical file system 
 
template <class TNodeData, class TLeafData>
class TreeIterator
{
// @dataprivate
private:
    // Attributes
 
    // @cmember tree to iterate on
    TreeRef                     m_tree;
    // @cmember current node
    TreeNodePtr                 m_pCurNode;
    // @cmember current leaf    
    TreeLeafPtr                 m_pCurLeaf;
 
// @funcpublic
public:
    // constructors, destructor
 
    // @cmember constructor for tree iterator; gets reference of the associated tree
    TreeIterator(TreeRef tree)
        : m_tree(tree), m_pCurNode(tree.getRoot()), m_pCurLeaf(NULL) 
        { m_tree.registerIterator(this); }
 
    // @cmember copy constructor for tree iterator
    TreeIterator(TreeIteratorRef iterRef)
        : m_tree(iterRef.m_tree), m_pCurNode(iterRef.m_pCurNode), m_pCurLeaf(iterRef.m_pCurLeaf)
        { m_tree.registerIterator(this); }
 
    // @cmember destructor notifies the tree
    virtual ~TreeIterator() { m_tree.unregisterIterator(this); }
 
public:
    // basic tree operations
 
    // @enum direction modes to iterate within tree
    enum TreeDirection 
    { 
        CURRENT,                // @emem no move
        UP,                     // @emem to parent node
        PREVIOUS,               // @emem to previous (left) sibling
        NEXT,                   // @emem to next (right) sibling
        FIRST_CHILD,            // @emem down to first sub node
        LAST_CHILD,             // @emem down to last sub node
        FORWARD,                // @emem forward in preorder (left down .. left down - right .. right - up - right - again)
        BACK                    // @emem back in preorder (left .. left - up - left - right down .. right down - again)
    };
 
    // @cmember set root node current (cd \)
    Bool                        gotoRoot()
        {  m_pCurNode = m_tree.getRoot();   m_pCurLeaf = NULL;  return (m_pCurNode != NULL); }          
    // @cmember set parent node current (cd ..)
    Bool                        gotoParent()
        {  m_pCurNode = m_pCurNode->getParent();  m_pCurLeaf = NULL;  return (m_pCurNode != NULL); }
    // @cmember find node by node data; search starts at current node
    Bool                        findNodeByData(TNodeData* pNodeData);
    // @cmember find node by name; search starts at current node; wildcards * and ? are allowed
    Bool                        findNodeByName(const String& searchName, Bool lookInSub=True);
    // @cmember find node by path; search starts at current node; wildcards are NOT allowed
    Bool                        findNodeByPath(const String& searchPath);
    // @cmember get name of current node; 
    String                      getCurrentNodeName() const;
    // @cmember get level of current node; 
    Int                         getCurrentNodeLevel() const;
    // @cmember get name of current leaf
    String                      getCurrentLeafName() const;
    // @cmember get node data 
    TNodeData*                  getCurrentNodeData() const;
    // @cemmber check if leaf is current
    Bool                        hasCurrentLeaf() const
        {  return m_pCurLeaf != NULL && (m_pCurLeaf->getParent() == m_pCurNode); }
    // @cmember check for younger brother
    Bool                        hasCurrentLeftNode() const
        {  return (m_pCurNode != NULL)? (m_pCurNode->getPrev() != NULL) : False; }
    // @cmember check for elder brother
    Bool                        hasCurrentRightNode() const
        {  return (m_pCurNode != NULL)? (m_pCurNode->getNext() != NULL) : False; }
    // @cmember check for children
    Bool                        hasCurrentKids() const
        {  return (m_pCurNode != NULL)? (m_pCurNode->getFirstKid() != NULL) : False; }
    // @cmember get path string of current node; the path string contains all node names of the parent up chain  
    //          beginning with the root node name and separated by the iterators path separator character e.g. '\'
    String                      getCurrentPath(Char cPathSeparator) const;
    // @cmember add next node to current chain
    Bool                        addNode(const String& name, TNodeData* pNodeData);
    // @cmember add to next level chain
    Bool                        addKid(const String& name, TNodeData* pNodeData);
    // @cmember insert node before current node 
    Bool                        insertNode(const String& name, TNodeData* pNodeData);
    // @cmember add leaf to current node
    Bool                        addLeaf(const String& name, TLeafData* pLeafData);
    // @cmember add leaf to parent node
    Bool                        addLeafToParent(const String& name, TLeafData* pLeafData);
    // @cmember insert leaf before current leaf
    Bool                        insertLeaf(const String& name, TLeafData* pLeafData);
    // @cmember delete current node
    Bool                        deleteCurrentNode(TreeDirection gotoAfterDelete=BACK);
    // @cmember delete current leaf
    Bool                        deleteCurrentLeaf(Bool gotoNextLeaf=True);
    // @cmember goto last node of (sub-)tree beginning at current node
    Void                        gotoLastNode();
    // @cmember goto next node in preorder (son, brother, uncle, grand uncle, ...)
    //  direction is forward or backward; search starts at current node or last node if backward     
    Bool                        gotoNextInPreorder(Bool startIteration, Bool includeLeafs = INCLUDE_LEAFS_FALSE);
    // @cmember goto previous node in preorder (son, brother, uncle, grand uncle, ...)
    //  direction is backward; search starts at last node and stops at current node
    Bool                        gotoPrevInPreorder(Bool startIteration, Bool includeLeafs = INCLUDE_LEAFS_FALSE);
    // @cmember go relatively to current node
    Bool                        gotoNode(TreeDirection direction = NEXT );
// @funcprivate
private:
    // @cmember iterator gets notified that a node was deleted
    Void                        notifyDeletion(TreeNodePtr pItemDeleted);
    // @cmember iterator gets notified that a leaf was deleted
    Void                        notifyDeletion(TreeLeafPtr pItemDeleted);
};
 
/////////////////////////////////////////////////////////////////////////////
// @class  TreeQuery
//   <nl>  Operates on a tree with nodes and leafs where any  
//   <nl>  node may be (unique) parent of a list of nodes and/or a list of leafs,
//   <nl>  e.g. the directory and file tree of a hierarchical file system 
 
template <class TNodeData, class TLeafData>
class TreeQuery
{
// @dataprivate
private:
    // Attributes
 
    // @cmember tree to iterate on
    TreeRef                     m_tree;
 
// @funcpublic
public:
    // constructors, destructor
 
    // @cmember constructor for tree iterator; gets reference of the associated tree
    TreeQuery(TreeRef tree);
};
#endif

Select allOpen in new window

Infinity08> What I meant was to store the nodes in an array...

I am not sure the original intention but your suggestion may be close to the implementation of a ballanced binary tree in an array that is used by Heap sort algorithm. See

http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
http://en.wikipedia.org/wiki/Heap_sort

The level order traversal is then simply iteration through the elements of the array from zero to max. Indices of the levels can also be easily computed.

>> A lot depends on the ratio of lookups versus inserts/deletes. If that ratio is sufficiently high, then the method I described is a good alternative.

Btw, that's often the case for a binary tree ... a lot more lookups than inserts ... ie. fill it once, then consult it often.

>>>> What I meant was to store the nodes in an array,
Yes, so did I understand it.  But I still see no benefits if doing so beside of the level traversion.

>> But I still see no benefits if doing so beside of the level traversion.

Which is what the question is about ;) But I agree :)

Hi Alex. You are right. It depends on where the extra pointer points to. All of this depends also on the original intention of niftyhawk.

Alex>> for (l = depth; l >= 0; --l)
{
    for (k = 1<<l; k < (1<<(l+1)); k++)
    {  
        mynode* next = root;
        for (n = 1; n < l; ++n)
        {
            if (k & (1<<(l - n)))
            {
       ..............

I think your solution is what I am really looking for. It is an iterative solution with no extra data structure. However, I am new to bitwise shifting and am confused. I didn't understand why you considered binary representation and why bitwise shifting was needed. Can't it be done without bitwise shifting considering the tree has all integers or strings?