Depth-first binary search tree traversal to set all values of a tree?

Question

So, I would wonder if it was easy to set all the values of a binary search tree in a simple inorder traversal, my thought being that since inorder traversal hits all the nodes anyway, and saves them in sorted order. Why not make it a generalized 'traverse' function that sets all the values, for instantaneous access later on?

My question: Is there a way to optimize this? Using iteration instead of recursion (edit: I know it is possible now, using a stack of pointers http://en.wikipedia.org/wiki/Tree_traversal#Implementations)

Can I modify it (or use a similar algorithm) to set successor, predecessor, or height of each node?

#include<iostream>
#include<list>
using namespace std;

class Node{
public:
    Node* left; 
    Node* right;
    Node* parent;
    int data;
    int level;
    bool isLeafNode;
    bool isLeftChild;
    bool hasLeftChild;
    bool hasRightChild;
    bool hasSibling;

public: Node(int x){
    right=NULL;
    left=NULL;
    parent=NULL;
    data = x;
    level=0;
    isLeafNode=false;
    isLeftChild=true;
    hasLeftChild=false;
    hasRightChild=false;
    hasSibling=false;
    }
};


class BinarySearchTree{
public: 
   Node* root; 
   list<int> inorder;
   int total; //total number of nodes
   int depth; //maximum level of any node in tree. Level of root is zero
   int total_leaf_nodes; //total number of leaf nodes
   int total_non_leaf_nodes;

public: BinarySearchTree(){
    root=NULL; 
    total=0;
    depth=0;
    total_leaf_nodes=0;
    total_non_leaf_nodes=0;
}


    void traverse(Node* p, int level){ //reset inorder, pass (root,0) to call.
           //go left i.e. 'L'
           if(p->left!=NULL) traverse(p->left, level+1);

           //visit Node i.e. 'V'
           total++;
           inorder.push_back(p->data); //pushes to last position
           p->level=level;
           if(level > depth) depth=level;


           if(p->left==NULL && p->right==NULL){
               p->isLeafNode=true;
               total_leaf_nodes++;
           }
           else{
              total_non_leaf_nodes++;
              if(p->left!=NULL)p->hasLeftChild=true;

              if(p->right!=NULL){    
                  p->hasRightChild=true;
                  (p->right)->isLeftChild=false;
              }

              if(p->left!=NULL && p->right!=NULL){
                  (p->left)->hasSibling=true;
                  (p->right)->hasSibling=true;
              }
           }

           //go right i.e. 'R'
           if(p->right!=NULL) traverse(p->right, level+1); 
    }
};

Could you please add more information on what you are trying to achieve? Why do you need to set all these pointers and values? Doing an iteration over all elements is linear operation and you can do a lot of things with a binary tree in the same complexity. — Ivaylo Strandjev, Oct 01 '14 at 07:53
possible duplicate of [recursion versus iteration](http://stackoverflow.com/questions/15688019/recursion-versus-iteration) — Jackson, Oct 01 '14 at 08:13
@Ivaylo Sorry if I wasn't clear, I just wanted to make one O(n) function to set all these values for all the nodes in the tree, for instantaneous access later on. I know that I can use iteration to prevent the function call overhead and a possible overflow, but I wanted to know if this method could also be modified to find out the successor or the height. — Algonaut, Oct 01 '14 at 08:25
My hunch is that the pointer lookups necessitated by storing the items in a `std::list<>` will dwarf any recursive function call overhead (which is essentially the same thing as using an explicit stack, except easier to program). The only way I can think of to get a possibly useful (though still at best constant-factor) improvement is to allocate the memory for the node data values from a contiguous array. Then you can write to this single contiguous block of memory to set all the values at once. — j_random_hacker, Oct 01 '14 at 10:15
Set node values ? To what and to accomplish what ? What is your real goal ? — Rerito, Oct 01 '14 at 11:45
@Rerito Like I said, for instantaneous access at a later time. It's difficult to explain exactly. This code started life as a question in my Algo 101 class, and I wondered if it was extendable. Basically, I just wanted a function that could be called every time I add a new node, to reset all the values of the tree that might have been changed afterwards. I was just wondering if it was possible to extend the simple inorder traversal function to also calculate height, sucessor, predecessor etc. of all the nodes, sort of get all the values you want in one fell swoop. — Algonaut, Oct 01 '14 at 12:18
So you want your method `traverse()` to compute the height of any node in your tree ? — Rerito, Oct 01 '14 at 12:27

Depth-first binary search tree traversal to set all values of a tree?

0 Answers0