In a recent pair of interviews, I was asked tree data structure questions, and I flubbed the first one. Hacking at a function that received a pointer to a node and that I needed to use as the launching point for recursion, not the recursive bit itself. Not pretty. NEXT time, I managed to gather up my wits, with a bit of help from my interviewer, Jim Gill, I managed to thread the needle and there it was, a recursive operation that worked. Sho-‘nuf! That original is at the bottom of this post- a complete, working version, follows this introduction. Its about 180 lines, with a lot of white space.
And here’s the deal. You can’t make a sensible recursive routine by simply getting the pointer and recalling that top level routine. YES recursion needs something that takes a pointer to node, and yes, you call it with a child of the original node. But there’s more to it. A non-recursive superstructure which supports a recursive heart.
So here’s a complete, working, version, that compiles and runs using “gcc” on Mac OS 10.5.8. It takes a bit more than what I started with. “C” and other versions will follow, as separate postings.
Macintosh-6:interview Bill4$ cat recursion_v.cpp
/* recursion_v.cpp */
/* Follow-up to ___ recursion problem with Jim Gill, web prowling question at ____ */
/* input:
(M)
| \
(N) (P)
| \ \
(Q) (S) (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S. P has one child – T.)
output:
Q, S, T, N, P, M
*/
#include <iostream>
#include <vector>
/* Structure in which the input data arrives: */
struct node {
std::vector <node*> children; std::string name;
};
/* Structure the result vector (array) is built from: */
struct nameNLevel {
std::string name; int level;
};
/*
* Synopsis: void recur( node* n, int level, std::vector* nsNLs )
* args:
* node* n this node, which has a name, may have children
* int level number of steps down the tree
* std::vector nsNLs pointer to the vector of node-name, level structs we’ll want to report
* returns:
* no return value. Node name and level are put into the vector of nameLevel structs.
* Mar 27, 2011 Bill Abbott
*/
void recur( node* n, int level, std::vector <nameNLevel>* nsNLs ){
/* To collect additions, nsNLs vector must be passed as a pointer! */
/* Unlike an array in C, an std::vector isn’t passed as a pointer automatically! */
nameNLevel* nNL = new nameNLevel;
nNL->name = n->name;
nNL->level = level;
nsNLs->push_back( *nNL );
int vecIdx = nsNLs->size() – 1;
// std::cout << nsNLs->size() << ” ” << vecIdx << ” “;
std::cout << (*nsNLs)[ vecIdx ].level << ” “;
std::cout << (*nsNLs)[ vecIdx ].name << ” “;
std::cout << (*nsNLs)[ vecIdx ].name.size() << ” “;
std::cout << (*nsNLs)[ vecIdx ].name.c_str() << ” “;
std::cout << (nsNLs->back()).name << ” ” << (nsNLs->back()).level << ” ” << n->name << ” ” << level << ” “;
std::cout << nsNLs->size() << ” ” ;
std::cout << n->children.size() << ” ” << (0 != n->children.size()) << “\n”;
if ( 0 != n->children.size()) { /* there are children */
for (int childCount =0; childCount < ( n->children.size()); childCount++ ){
recur( n->children[childCount], level+1, nsNLs ); /* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!= */
} /* recur *
/*
* Synopsis: void passThrough( node* n )
* args:
* node* n this node, which has a name, may have children
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011 Bill Abbott
*/
void passThrough( node* n ) {
std::vector namesNLevels;
int level = 0;
recur( n, level, &namesNLevels );
std::cout<< namesNLevels.size() << ” ” << “\n”;
int maxLevel = 0;
for (int i=0; i < namesNLevels.size(); i++ ) {
std::cout<< maxLevel << ” ” << i << “\n”;
if (namesNLevels[i].level > maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */
/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */
for (level=maxLevel; level >= 0; level–){
for (int i=0; i < namesNLevels.size(); i++ ) {
if (namesNLevels[i].level == level){
std::cout << namesNLevels[i].name << ” “;
} /* if (namesNLevels…) */
} /* for i */
} /* for level */
printf( “\n”);
}
/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int argc count of command line arguments
* char* argv[] vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011 Bill Abbott
*/
int main( int argc, char* argv[] ) {
/* 3 level b tree:
* M has two children, N and P, and
* N has two children, Q and S.
* Q has no children
* S has no children
* P has one child – T.
* T has no children
*/
node* T = new node;
T->children.clear();
T->name = “T”;
node* S = new node;
S->children.clear();
S->name = “S”;
node* Q = new node;
Q->children.clear();
Q->name = “Q”;
node* P = new node;
P->children.push_back(T);
P->name = “P”;
node* N = new node;
N->children.push_back(Q);
N->children.push_back(S);
N->name = “N”;
node* M = new node;
M->children.push_back(N);
M->children.push_back(P);
M->name = “M”;
passThrough( M );
return( 1 );
————- Example output, with my debug couts—————-
Macintosh-6:interview Bill4$ c++ recursion_v.cpp
Macintosh-6:interview Bill4$ a.out
0 M 1 M M 0 M 0 1 2 1
1 N 1 N N 1 N 1 2 2 1
2 Q 1 Q Q 2 Q 2 3 0 0
2 S 1 S S 2 S 2 4 0 0
1 P 1 P P 1 P 1 5 1 1
2 T 1 T T 2 T 2 6 0 0
6
0 0
0 1
1 2
2 3
2 4
2 5
Q S T N P M
Macintosh-6:interview Bill4$
————————– Here’s how this started:——————–
Ok- it was whiteboard code and didn’t compile. I’m working on that. Staring with std::vector blahblah which seems like some really kewl Java/C++ library good stuff. What Kernighan and Ritchie were hoping for.
input:
(M)
| \
(N) (P)
| \ \
(Q) (S) (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S. P has one child – T.
output:
Q, S, T, N, P, M
typedef struct node {
std::vector <node*> children; std::string name;
}
typedef nameNLevel {
std::string name; std::int level;
}
void passThrough( node* n ) {
std::Array namesNLevels;
int level = 0;
recur( n, level, namesNLevels );
int maxLevel = 0;
for (int i=0; i
if (namesNLevels[i].leve l> maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */
/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */
for (level=0; level =<maxLevel; level++){
for (i=0; i<
if (atoi(namesNLevels[i].name) == level){ printf( “%s “, namesNLevels[i].name } /* longer but more robust */
} /* for i */
} /* for level */
printf( “\n”);
}
void recur( node* n, integer level, std::Array nsNLs ){
/* its an array, gets passes as a pointer anyhow */
nsNLs.pushback( new nameNLevel( n->name, level));
if ( 0 != n->children.count()) { /* there are children */
for (int childCount =0; childCount < ( n->children.count()); childCount++ ){
recur( n->children[childCount], level+1, nsNLs );
/* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!= */
}
A nice page at IBM regarding recursion:
http://www.ibm.com/developerworks/linux/library/l-recurs.html#
Good stuff!
bill abbott's weblog 