v.vinay.k
BAN USER
Questions (1)
Comments (2)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I have an approach.
Given binary tree with root node *rootBin;
1. Traverse the given binary tree by any traversal methods and push the node value to a linked list. Make sure that the nodes are pushed in sorted manner.
2. Now we have a linked list in sorted order
3. Now write a function binaryToBST which takes actual pointer to root node of binary tree.
Traverse the tree in in order traversal format. similary get the sorted values from list one by one.
binaryToBST(rootNode->left);
rootNode->data = (*head)->value; // value is from linked list
*head = (*head)->next;
binaryToBST(rootNode->right);
I didnt write the entire code. I will update the code once I write and test it.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Algorithm:
- v.vinay.k January 12, 20141. Traverse the tree in level order fashion.
2. Set a flag to 0 initially. Flag is used to check if any leaf node is encountered.
3. Mark end of each level with NULL node.
4. When leaf node is encountered for the first time, set the flag to 1.
5. Traverse tree, and if any non leaf node is occured and flag is already set to 1, then it failes the conditoin
6. If NULL node is encountered indicating the end of a level and If the flag is set indicating leaf node is already occured then verify if queue is empty or not. If not then tree fails the condition.