CareerCup

I think in above he is also saying about indexes not ascii values

This is silly too.

Storing as per the index value will make it a Linked list not a BST, as every next index will be greater than previous

BST means, node->left <= node <= node->right.
You can not store the actual characters in a bst in a way that it meats the criteria above as well as the original string can be formed by any of inorder, preorder or postorder.

The answer is to form bst using index of characters in the string.

Its not my question. I read this on the glassdoor. I have mentioned the link above.

@Bevan: Please don't post such bad questions like these, especially if you are getting it from some other site. There is no scope for gauging what the interviewer had in mind.

In fact, look at the upvoted answers. They are all so trivial...

@Loler. Yep. I am sorry.

This is just silly to be the answer for an interview question from amazon.

glassdoor. com /Interview/Gave-a-string-of-characters-and-asked-them-to-store-in-a-binary-search-tree-in-such-a-way-that-it-can-be-extracted-in-exact-QTN_163554.htm

In this method, the BST creation operation will be O(n logn) as we will need to keep finding the median for each insertion.
Instead we can use preorder bread first traversal for insertion. Will be O(n)

awesome approach jtr.hkcr . I try implementing it just to see if i could ( didn't check for bugs though ). I am a senior in college and I am trying to transition from college style coding ( check for correct results only) to industry style ( correct result + best practices ) so if you find flaws in my style, don't hesitate to mention them.

struct Node 
{
	char character;
	struct Node *left;
	struct Node *right;
}

struct Node * create_bst(char * array )
{
	if( ! array )
		return NULL;

	int size = strlen(array);
	int limit = size / 2;
	struct Node *root = build_left_side(array, 0, limit); // left side include middle element
	root->right = builder_right_side(array, ++limit, size - 1);
	return root;
}

/* chars forming the left side are from index start to end */
static struct Node * build_left_side(char * array, int start, int end)
{
	struct Node *root = create_node(array[start++]);

	while( start <= limit )
	{
		struct Node *node = create_node(array[start++]);

		if ( root->right )
		{
			node->left = root;
			root = node;
		}
		else
		{
			root->right = node;
		}
	}
}

/* chars forming the right side are from index start to end */
static struct Node *build_right_side(char *array, int start, int end)
{
	struct Node *root = create_node(array[end--]);
	
	while( end >= start )
	{
		struct Node *node = create_node(array[end--]);
		if( root->left )
		{
			node->right = root;
			root = node;
		}
		else
		{
			root->left = node;
		}
	}
	return root;
}

/* create a new bst node with char c as value */
struct Node * create_node( char c)
{
	struct Node *node = malloc(sizeof(struct Node *));
	if( ! node ) 
		msg_malloc_failed(); 

	node->character = c;
	node->left = NULL;
	node->right = NULL;
	return node;
}

/* print mem error msg and exit */
void msg_malloc_failed()
{
	printf("malloc failed \n");
	exit(-1);
}

Hi Jean,
Thanks, code for BFS insertion and traversal is provided in a separate comment. Search for create_string_tree() and get_string_from_tree() functions in this page.

This is really LOL. -1 from me. Sorry.

Why not make a linked list while you are at it? (It is a tree too...)

@loler cause it's an interview and that's what you were asked to do( probably to test your understanding of bst + coding skills ) But I do agree though that there needs to be clarifications from the interviewer about the purpose of the tree. are you just making a bst lookalike or are you going to use the tree you build later ( search, insert , remove) ?
if you are going to use that tree, then the bst node should be modify to store a key in order to agree with definition of bst. For this implementation, the array index of each char would make a perfect key.

@jean. That is what people have _interpreted_ it to be. Which IMO, is a totally bogus interpretation. If you want to put the characters in a BST, then isn't it reasonable to assume you want to make the character the key?

Usually interview questions have the scope for the candidate to show a logical thought process. btw, if the interviewer was only interested in BST+coding, do you really think the interviewer could not find anything better than such a borderline nonsensical question?

Making the index the key, is just arbitrary. In fact, making it a BST like that (using the position) gains you what exactly? Leaving it as an array is much better if you want to lookup etc.

More likely, the person who posted on Glassdoor was completely clueless and had no idea what the interviewer was asking, and posted some nonsense, which Bevan chose to post here.

That is what is annoying about some of problems posted here. They are just incomplete and bordering on the nonsensical (at least from a practical programming interview question point of view).

What makes it funny(and annoying at the same time) is people seem to delude themselves by posting and upvoting trivialities (I guess this might make me sound arrogant). If people are interested in getting a job at a good company, they should learn to be critical of their solutions and give the questions themselves some credit. Coming up with nonsensical/trivial interpretations will easily get you a reject.

That was a long rant. Sorry.

yes it is reasonable first to assume characters will be keys for bst. but you know common strings have repeated chars( in diff patterns). how do you deal with that to ensure the right order when u do an inorder traversal of the tree ? e.g: dafa => "aadf" inorder in normal bst.

finally about these kind of ambiguous question in interviews :
my opinion is the employer wants to figure out
what kind of problem solver are you ?
are you the kind that will complain to the clients about their requirements(because they dont fit the standard way you expect things to work) and make them leave OR are you the kind that can adapt and deliver a product/solution that fits the client's requirements.

hypothetically if we were auditioning for a contract and this question was the requirement: your answer to the client would be "sorry i can't. my bst does not work for this purpose" and I will say "yes here is the product". Guess who gets the contract !

@Jean: If you say yes here is your product, and give a solution without clarifying anything, then there is no guess, you will get rejected.

You have to clarify the problem further, and that is not possible because Bevan just copied and pasted from glassdoor, giving no chance to try and asking clarifying questions.

I am not claiming that if some ambiguous question is given you throw up your hands claiming nonsense etc (not sure how in the world you came to that interpretation). In any case, you need to have the guts to call crap for what it is...

Anyway, pointless discussion...

Yes, otherwise the problems seems just too trivial, and likely OP has not given us enough details.

Alas, seems like people want to take the *trivial* way out. I am deleting this answer, as the question has no scope of getting clarified.

2,3,1. This cannot be the preorder of any BST.

Everything is good with solution but I think Interviewer asked for a BST ?? except that solution is perfect

Think we need to know why there is a BST requirement. There is no mention of a search operation too. Could Bevan please detail why a BST is needed? Should the characters be ordered in alphabetical order in the tree?

Yes I think You are right, Question might be incorrect...There is no purpose of search operation in the question...Probably its just the Binary Tree

i don't know the language you are using. is it c# ?
can you explain your algo for building the tree with a queue ? looks interesting

Hi Jean,
This is C++ (Except for the usage of STL queue container class, this is C code. Didnt want to write code for queue in C).

Logic:

Node *create_string_tree(const char * str)

BFS traversal is => First root, then roots left child, then roots right child, then roots left childs left child, and so on. Shown below

1. root
    2. root->left
    3. root->right
    4. root->left->left
    5. root->left->right
    6. root->right->left
    7. root->right->right
    8. root->left->left->left
    9. root->left->left->right
    10. root->left->right->left
    ...and so on

queue<Node **> insert_q is used to keep track of this order. We will insert the address of left or right pointer in this queue and hence "Node **".

Root of the binary tree will be the first character in the string. Once the root node is created, the next elements will be inserted to the left child pointer first, then the right pointer. Hence adding them to the insert_q in that order.

For loop will run through the rest of the characters in the string. For each character in the string, for loop will
- Insert each of them to the first address from the insert_q (and removes that address from the queue).
- Once the node for a character is attached to the tree, we put that nodes left and right address to the queue for future insertion.

Once all the characters are inserted, insert_q is discarded and the root pointer is returned.

This is the logic of create_string_tree(). Logic for get_string_from_tree() is similar except that we use a queue of "Node *" instead of "Node **" as the operation is only reading the elements from tree.
Hope this description is clarifies. Thanks.

u r a bad loser, now ain't that true..haha

Interviewer will react by fucking you big time.