• Status: Solved
• Priority: Medium
• Security: Public
• Views: 2427

# Print Balanced Tree nodes using level order traversal from bottom up

Hi..I have a balanced tree like this:
1
2         3
5   6     7   8

I have the following code to print level order traversal from top to bottom (ie. 1235678) . The code uses a queue to print it. However, how can I modify the code as to NOT use recursion and NOT use an extra datastructure (like the array queue which I am using), but still print the tree bottom up in a level order traversal ? The output should be something like this:

5678231

// Level order traversal..
void levelOrderTraversal(mynode *root)
{
mynode *queue[100] = {(mynode *)0}; // Important to initialize!
int size = 0;
int queue_pointer = 0;

while(root)
{
printf("[%d] ", root->value);

if(root->left)
{
queue[size++] = root->left;
}

if(root->right)
{
queue[size++] = root->right;
}

root = queue[queue_pointer++];
}
}

Thanks
0
niftyhawk
• 6
• 5
• 5
• +1
1 Solution

Commented:
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.
0

Commented:
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;
}
``````
0

Commented:
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" ...
0

Commented:
>>>> 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
0

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

Commented:
>>>> 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.
0

Commented:
>> 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.
0

Commented:
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.
0

Commented:
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.
0

Commented:
>>>> 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
{ 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
``````
0

Commented:
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.
0

Commented:
>> 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.
0

Commented:
>>>> 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.
0

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

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

Commented:
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.
0

Author Commented:
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?
0

Commented:
>>>> for (l = depth; l >= 0; --l)

the outer loop goes from depth (== deepest level, in my sample depth == 3) to 0. The last iteration would assign root to next and print root data.

>>>>    for (k = 1<<l; k < (1<<(l+1)); k++)

1<<l   shifts the bits of the number 1 (1 == 00000001 in binary representation) l positions to the left. '1' has only one bit, the lowest bit at the right, so the result in binary is (for l == 3)  00001000, what is 8 in decimal. So, bit-shifting the 1 to the left for l positions is equivalent to taking 2 to the power of l:  2^3 == 8. That is what I intended. If you look at the binominal tree, you see that the first number of each level is a power of 2. Hence (1<<l) can be used to calulate the first position in that level.  Same happens with   (1<<(l+1)). Here I calculate the next power, thus getting an upper boundary for the iteration at the current level.

>>>>        mynode* next = root;
to search the node for the current level position I have to start at the top again.

>>>>        for (n = 1; n < l; ++n)
The loop runs from 1 to the current level, in the sample it runs from 1 to 3, what is 3 times. Starting from root I hvae to change the level 3 times to come down to the current level.

>>>>            if (k & (1<<(l - n)))
Now, it gets nifty.  'k' is the position I want to look-up. The binary representation of   that number tells now, whether i have to go left or right in the binary tree:

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

Look at the most left branch. It was a left shift of the most significant bit of the root. The left child of root has a 0 bit at the most right pos. Looking at the subtree where that child is root of, you see that the 0 bit was moved to pos 2 (we always count from the right when talking from bits and starting with base = 0) for all items of the bottom level. Check the right subtree and you see that all numbers of the bottom level have a 1 bit at pos 2. So, that bit 2 determines whether I have to go left or right when starting from root. The same happens one level deeper now it is the bit at pos1 of the bottom level numbers which says whether to go right or left, and finally it is the bit 0 which says what to when branching to the bottom level.

>>>>            if (k & (1<<(l - n)))

Coming back to the statement. (1<<(l - n)) raises 2 to the power of (l-n) as discussed above. We have l  == 3 and n == 1 at begin, so we have 4 == 0100 for  (1<<(l - n)) . That exactly is bit 2 (the 3rd from the right). The '&' operator compares bits and, if we have 1101 & 0100, the result is
0100 as only that bit will get 1 where both operands have a 1 as well. The & operator therefore is used to 'test' whether a bit at a given position was set or not.

'if (k & (1<<(l - n)))' checks whether the given k (0xD == 1101) has the bit at pos l-n  (== 2) set, and the result is non-zero, what means 'true'. So, the if condition is true and we goon turning to the right subtree. for the next iteration n was 2, so l-n is 1, and we are testing bit 1 of theoriginal number, whether to go right or left. The bit is 0, so we go left. Finally we test for bit 0 what is 1 and go right and have our number found...

Regards, Alex
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.