All parents of a node in BST?

Question

While printing Binary Search Tree(BST) using recursive function (pre-order). I need to print all the parents(path form root) of current node.
An auxiliary data structure can(e.g. path in my code) be use but I don't want to keep node->path to store path.

      4                           
     / \  
    /   \  
   2     6
  / \   / \
 1   3  5  7  

Suppose I am printing nodes in rows using pre-order traverse:

NODE    PATH  
4       4  
2       4,2  
1       4,2,1
3       4,2,3       
6       4,6
5       4,6,5
7       4,6,7  

I did as follows: Working fine!
Path end with 0 (Zero) value in this code. And there is no node value is 0 in BST.

void printpath(int* mypath){
   while(*mypath)  
      printf("%d ", *mypath++);  
}

void preorder(struct tree *p, int* path){
    int *mypath = calloc(sizeof(path)/sizeof(int) + 1 , sizeof(int*));
    int* myp=mypath;

    if(p!=NULL){  
       while( *myp++ = *path++ );  
       --myp;
       *myp=p->data;
       *(myp+1)=0;

        printf("%d PATH ",p->data);
        printpath(mypath);
        printf("\n");
        preorder(p->left, mypath);
        preorder(p->right, mypath);
    }
    free(mypath);
}

But I don't want to keep path array as there is lots of nodes in BST. Can some one suggest me other data-structure/ or method ? A suggestion would be enough but should be efficient.

Ana

as far as I can see you will need to keep some kind of structure to keep track of paths, and your path array actually seems the simplest possible idea. An alternative would be to have each node keep a pointer to its parent, but this of course would "waste" this space always, not just when printing. You can do without allocation and print using constant space in this way though. – Sordino

@YefimDinitz : Thanks for you suggestions :) ... The actual Data-Structure(DS) much more complicated then BST. I used the term BST to keep problem statement simple so I like to avoid parent pointer...may be any dynamic DS would be useful but its hard to maintain :( . – Ana

What I tried was passing a string containing all the nodes up to the current one that are in the path and the node to look at. You would concatenate the passed node's information to the string, then print out the node's data and the new string. Then perform the same function on it's children passing the new string. It works well, but may not be the way you want to implement it as I had to use a stringstream to concatenate the integer to the string. – Rident

Answer 1

Here's an old trick, which still works: keep the back pointers in the call stack.

    struct stacked_list{
      struct stacked_list* prev;
      struct tree* tree; 
    };

   void printpath_helper(int data, struct stacked_list* path) {
      if (!path->prev)
        printf("%d PATH ", data);
      else
        printpath_helper(data, path->prev);
      printf("%d ", path->tree->data);
    }

    void printpath(struct stacked_list* path) {
      printpath_helper(path->tree->data, path);
      putchar('\n');
    }

    void preorder_helper(struct stacked_list* path) {
      if (path->tree) {
        printpath(path);
        struct stacked_list child = {path, path->tree->left};
        preorder_helper(&child);
        child.tree = path->tree->right;
        preorder_helper(&child);
      }
    }

    void preorder(struct tree* tree) {
      struct stacked_list root = {NULL, tree};
      preorder_helper(&root);
    }

Each recursion of preorder_helper creates an argument struct and passes its address to the next recursion, effectively creating a linked list of arguments which printpath_helper can walk up to actually print the path. Since you want to print the path from top to bottom, printpath_helper needs to also reverse the linked list, so you end up doubling the recursion depth of the function; if you could get away with printing bottom to top, printpath_helper could be a simple loop (or tail recursion).

Drummond

Answer 2

You can use a single array to keep the parents of the current node and pass it down when doing the recursion instead of creating a new array, just remember to resume the array when one recursion finished. I think in that way you can save a lot of memories. The code is below:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct node
{
    int data;
    struct node *left, *right;
};

// A utility function to create a node
struct node* newNode( int data )
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;
    temp->left = temp->right = NULL;

    return temp;
}



void print_preorder_path(struct node *root,vector<int>& parents)
{
     if(root!=NULL)
     {
              cout<<root->data<<"\t";
              for(size_t i=0;i<parents.size();++i)cout<<parents[i]<<",";
              cout<<root->data<<endl;

              parents.push_back(root->data);
              print_preorder_path(root->left,parents);
              print_preorder_path(root->right,parents);
              parents.pop_back();

     }
}

int main()
{
     // Let us construct the tree given in the above diagram
    struct node *root         = newNode(4);
    root->left                = newNode(2);
    root->left->left          = newNode(1);
    root->left->right         = newNode(3);
    root->right               = newNode(6);
    root->right->left         = newNode(5);
    root->right->right        = newNode(7);

    vector<int> parents;

    cout<<"NODE\tPATH"<<endl;
    print_preorder_path(root,parents);

    getchar();
    return 0;
}

The code is written with stl for simplicity, you can modify as you need, hope it helps!

Striction

nice one ..this is the way I thought I would be implement..Thanks! – Ana