Developer
BAN USERIt looks like you didn't acknowledge the problem statement correctly. The problem statement says it is a BST, not a binary tree. In fact the sample you give is incorrect with this constraint because the first tree is not a BST.
ABG is correct, you can rebuild a BST with just a preorder or postorder traversal, assuming the ordering is implicit in the traversal,i.e., integers or characters. Plus you use a consistent rule for duplicates, if they are allowed.
tristan.uva, I believe you are on the right track with a postorder traversal, but your assumption that the only time you have a duplicate is when the root and child are equivalent is not correct.
Consider the following BST;
Start State:
C
/
C
/
A
\
C
Final State:
C
/
A
\
C
kirubakaran1989
Your answer is not correct.
It's not true that n!/n, equivalent to (n-1)!, permutations are going to be min-heaps. It's easily demonstrated by just adding the element 10 to your example.
Given the array 1,2,3,10, there are (4-1)! = 3! = 6 permutations with min element as the first element. But only 2 of those permutations are min-heaps. 1,2,3,10 and 1,3,2,10.
This code is easy to remember because it is similar in structure to the recursive version. Uses a single stack with bool flag embedded in node to track state of node.
Simple, neat and petite.
template<class T>
struct Node {
Node(T _data) : item(false),data(_data),
left(0), right(0){}
Node() : item(false),data(), left(0), right(0){}
Node* asItem() { item=true; return this;}
Node* asLink() { item=false; return this;}
bool isItem() const {return item; }
bool item; T data; Node* left; Node* right;
};
typedef Node<int> Tree;
void postOrderIterative(Tree* root) {
if(!root) return;
std::stack<Tree*> s; s.push( root->asLink() );
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
std::cout << root->data << std::endl;
} else {
s.push( root->asItem() );
if( root->right ) s.push(root->right->asLink());
if( root->left ) s.push(root->left->asLink());
}
}
}
Iterative post-order traversal with one stack, one flag per node, O(n) time complexity. This is a duplicate question, see question# 10212756, you might also want to look over there and review that discussion.
template<class T>
struct Node {
Node(T _data) : item(false),data(_data),
left(0), right(0){}
Node() : item(false),data(), left(0), right(0){}
Node* asItem() { item=true; return this;}
Node* asLink() { item=false; return this;}
bool isItem() const {return item; }
bool item; T data; Node* left; Node* right;
};
typedef Node<int> Tree;
size_t findBSTHeight(Tree* root) {
if(!root) return 0;
size_t maxHeight=0;size_t height=0;
stack<Tree*> s; s.push(root);
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
maxHeight = max(maxHeight,height);
--height;
} else {
++height;
s.push(root->asItem());
if( root->right ) s.push(root->right);
if( root->left ) s.push(root->left);
}
}
return maxHeight-1;
}
I use a flag per node, but only one stack to accomplish a post-order iterative traversal. O(n) time complexity, space complexity depends on how you keep track of the node state. I kept it simple and just used a bool.
The basic algorithm is simple and easy to understand and if you needed to do a pre-order or in-order traversal it can easily be adapted by simply reordering how the nodes are pushed onto the stack. Very similar to what we do with recursive algorithms. Simple, slick and neat.
template<class T>
struct Node {
Node(T _data) : item(false),data(_data),
left(0), right(0){}
Node() : item(false),data(), left(0), right(0){}
Node* asItem() { item=true; return this;}
Node* asLink() { item=false; return this;}
bool isItem() const {return item; }
bool item; T data; Node* left; Node* right;
};
typedef Node<int> Tree;
size_t findBSTHeight(Tree* root) {
if(!root) return 0;
size_t maxHeight=0;size_t height=0;
stack<Tree*> s; s.push( root->asLink() );
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
maxHeight = max(maxHeight,height);
--height;
} else {
++height;
s.push(root->asItem());
if( root->right ) s.push(root->right);
if( root->left ) s.push(root->left);
}
}
return maxHeight-1;
}
void preOrderIterative(Tree* root) {
if(!root) return;
std::stack<Tree*> s; s.push(root);
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
std::cout << root->data << std::endl;
} else {
if( root->right ) s.push(root->right);
if( root->left ) s.push(root->left);
s.push( root->asItem() );
}
}
}
void inOrderIterative(Tree* root) {
if(!root) return;
std::stack<Tree*> s; s.push(root);
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
std::cout << root->data << std::endl;
} else {
if( root->right ) s.push( root->right);
s.push( root->asItem() );
if( root->left ) s.push( root->left);
}
}
}
A simple one that I can remember off the top of my head, attributed to Brian Kernighan is the following;
unsigned int countBitsSet(unsigned int v) {
unsigned int c=0;
for(; c; ++c)
v &= v-1;
return c;
}
Each iteration of the for loop strips off the lowest bit set. So if you have a sparse bit value this is fast and if not it can be slow, but it is correct. Several ingenious optimizations have been devised. Reference "Hacker's Delight" by Henry S. Warren Jr. ISBN 0-201-91465-4 and also search for "Bit Twiddling Hacks" by Sean Anderson on the web.
- Developer August 10, 2011I've seen the remark, "+ve & -ve numbers," in other postings. I'm unfamiliar with this notation. I assume the questioner intends to mean "signed integers." If that's true, why the reference to +ve and -ve? Why not just say signed integers or even just integers which is the more common usage?
Thanks to anyone who responds.
This is one of those questions that simply make me go WTF? I wouldn't respond that way in an interview, at least I hope I wouldn't. What I would do is ask the interviewer for clarification
At this time my opinion of this question is that it is a crappy question. Now I could just be barking at the moon mad because I just don't get it. I've come across questions like that before that looked 'crappy' that eventually turned out to be quite good, I just didn't understand the context.
Maybe someone else has seen this question before and can at least explain what the context of this question is, or give enough clarification to magically transform it from a crappy question to one that is enlightening.
I don't think depth should be static and from your pseudo code it's not clear how you're iterating through the children, but it's certainly on the right track and very similar to what I have.
struct Node;
typedef std::list<Node*> NodeList;
struct Node {
int data;
NodeList children;
}
int findMinDepth( Node* root ) {
if ( !root || root->children.empty() ) return 0;
int minDepth = MAXINT;
for ( NodeList::const_iterator
it = root->children.begin();
it != root->children.end();
++it ) {
int depth = findMinDepth(*it);
if ( depth < minDepth ) minDepth = depth;
}
return 1 + minDepth;
}
The statement "WITHOUT using the ascii values" probably means you can't use the ascii value directly, especially with the constraint of an array of size 32. Since the poster hasn't clarified the issue, it is probably safe to assume you can use the ascii values to determine an indirect index. Especially since you only have to worry about lower case. Which means you only need 'z'-'a'+1 slots or 26 slots. So an array of size 32 is going to be more than sufficient to track lowercase letters. So something like the following pseudo-code should do the trick.
for (char* c = buffer; c < 'buffer end'; ++c ) {
array[*c-'a']++;
++c;
}
This also assumes you're using single byte characters, which again since the poster hasn't specified is probably a safe assumption to make, but... depends on whomever was the originator of the question.
- Developer July 04, 2011Pritesh suggestion is in line with the more traditional solution and is called the 'Named Constructor Idiom.'
Search the net for the C++ FAQ by Marshall Cline. Check out FAQ [16.21] which answers the following question.
"How can I force objects of my class to always be created via new rather than as locals or global/static objects?"
This technique is also commonly used with the 'Factory Pattern.'
zhaoyangster that looks correct.
I have one variation/minor improvement to suggest, use c=c&c-1 instead of c=c>>1 and you only loop once for each bit, instead of all the bit positions.
{{
int bit_swaps_required( int a, int b ) {
unsigned int count = 0;
for( int c = a ^ b; c != 0; c = c & c-1 ) {
++count;
}
return count;
}
}}
Guest123,
- Developer August 30, 2011You didn't read the problem statement correctly. It's a Binary Search Tree (BST) not just a Binary Tree (BT). If it is a BST then you can reconstruct the unique BST with just the preorder traversal.
You are correct for a BT, with one caveat. The nodes need to be uniquely labeled, so you can't have any duplicate labels. If you have duplicate labels, you can't reconstruct the unique BT with any combination of preorder, inorder or postorder traversals.
It's possible to reconstruct the BT when it has duplicate labels, but you need additional data in order to be able to discriminate the duplicate labels correctly.