what should be the structure of binary search tree node

Question

i am trying to make c++ program for binary search tree which will contain following functionality (actually this is a part of my college assignment):

A) CREATE Binary search tree.

B) Inorder, preorder, postorder traversals. ( non-recursive )

C) Search the Val in tree.

D) Breadth first traversal.

E) Depth first traversal

F) Count leaf nodes, non-leaf nodes.

G) Count no. of levels

my doubt is:-

1. usually a tree node have following structure:

class node{

 private:
   node *lChild;
   int info;
   node *rChild;
}

so in case i want to perform depth-first or breadth-first traversal can i change the node structure and add one more pointer pointing to the parent so that i can easily move backward in the hierarchy

class node{

 private:
   node *parent //pointer to parent node
   node *lChild;
   int info;
   node *rChild;
}

is this considered as normal practice or bad form of programming a binary tree ? and if it is not considered as good way of programming a tree is there any other way or do i have to use the method given in books of using stack (for Depth First) and queue(for breadth first) to store nodes (visited or non-visited accordingly)

2. This is first time i am learning data structures so it will be a great help if someone can explain in simple words that what is the difference between recursive and non-recursive traversal with binary tree in consideration

Answer 1

i change the node structure and add one more pointer pointing to the parent [...] is this considered as normal practice or bad form of programming a binary tree ?

It is not a normal practice (but not quite "bad form"). Each node is a collection of data and two pointers. If you add a third pointer to each node, you will have increased the overhead of each node by 50% (two pointers to three pointers per node) which for a large binary tree will be quite a lot.

This is first time i am learning data structures so it will be a great help if someone can explain in simple words that what is the difference between recursive and non-recursive traversal

A recursive implementation is a function that only applies on a node, then calls itself for the subsequent nodes. This makes use of the application call-stack to process the nodes of the tree.

A non-recursive implementation uses a local stack to push non-processed nodes; then it loops as long as there is data on the stack and processes each entry.

Here's an example for printing to console, that shows difference between recursive and non-recursive ( the example is incomplete, as this is homework :] ):

void recursive_print(node* n) {
    std::cout << n->info << "\n";
    if(n->lChild)
        recursive_print(n->lChild); // recursive call
    // n->rChild is processed the same
}
void non_recursive_print(node* n) {
    std::stack<node*> stack;
    stack.push(n);
    while(!stack.empty()) { // behaves (more or less) the same as 
                            // the call-stack in the recursive call
        node* x = stack.top();
        stack.pop();
        std::cout << x->info << "\n";
        if(x->lChild)
            stack.push(x->lChild); // non-recursive: push to the stack
        // x->rChild is processed the same way
    }
}
// client code:
node *root; // initialized elsewhere
if(root) {
    recursive_print(root);
    non_recursive_print(root);
}

Answer 2

1. You don't need a pointer to the parent node. Think about the cases when you would use it. The only way you can reach a node is through its parent, so you have already visited the parent.

2. Do you know what recursive means?

Answer 3

There's nothing to stop you adding a parent pointer if you want to. However, it's not usually necessary, and slightly increases the size and complexity.

The normal approach for traversing a tree is some kind of recursive function. You first call the function and pass in the root node of the tree. The function then calls itself, passing the child pointers (one at a time). This happens recursively all the way down the tree until there are no child nodes left.

The function does whatever processing you want on its own node after the recursive calls have returned. That means you're basically traversing down the tree with each call (making your call stack progressively deeper), and then doing the processing on the way back up as each function returns.

The function should never try to go back up the tree the same way it came down (i.e. passing in a parent pointer), otherwise you'll end up with an infinite recursion.

Answer 4

Typically you only need a parent pointer if you need to support iteration Imagine that you have found a leaf node and then want to find the next node (lowest key greater than current key), for example:

mytree::iterator it1=mytree_local.find(7);
if (it1 != mytree_local.end())
{
    mytree::iterator it2=it1.next();  // it1 is a leaf node and next() needs to go up
}

Since here you are starting at the bottom and not the top, you need to go up

But your assignment only requires operations that start at the root node, you shouldn't have a up pointer, follow the other answers for approaches that avoid the need to go up.

Answer 5

I would suggest you look into the Visitor pattern - for its flavor, not specifically for its structure (it's very complex).

Essentially, it is a design pattern that disconnects traversal of a tree in such a way that you have only one set of code that does tree traversal, and you use that set of code to execute various functionality on each node. The traversal code is generally not part of the Node class.

Specifically, it will allow you to not have to write the traversal code more than once - For example, utnapistims answer will force you to write traversal code for every piece of functionality you need; that example covers printing - to ouputXML() would require another copy of traversal code. Eventually, your Node class becomes a huge ungainly beast.

With Visitor, you would have your Tree and Node classes, a separate Traversal class, and numerous functional classes, such as PrintNode, NodeToXML, and possibly DeleteNode, to use with the Traversal class.

As for adding a Parent pointer, that would only be useful if you intended to park on a given node between calls to the Tree - i.e. you were going to do a relative search beginning on a pre-selected arbitrary node. This would probably mean that you had better not do any multi-threaded work with said tree. The Parent pointer will also be difficult to update as a red/black tree can easily insert a new node between the current node and its "parent".

I would suggest a BinaryTree class, with a method that instantiates a single Visitor class, and the visitor class accepts an implementation of a Traversal interface, which would be one of either Breadth, Width or Binary. Basically, when the Visitor is ready to move to the next node, it calls the Traversal interface implementation to get it (the next node).