Q1. Given a Preorder traversal of a Binary Search Tree, reconstruct the tree.
Hint: First node is root. Scan the traversal till we get a value greater than the root. Then, the left part forms the left subtree whereas right part forms the right subtree.
Q2. Given a Preorder traversal of a Binary Search Tree, design an algorithm to verify if each non-leaf node has only one children.
Hint: a) If a node has only one children then all its children are greater ( for right subtree) or lesser ( for a left subtree ) than it. IN preorder traversal all the children of a node comes after the node. So, we just need to check if all the nodes are greater or lesser. To do it efficiently, we can use the property that the largest node is the rightmost node whereas the smallest node is the leftmost node.
b) Construct a BST from Preorder traversal. First node is root. Scan the traversal till we get a value greater than the root. Then, the left part forms the left subtree whereas right part forms the right subtree.
Q3. Two nodes in a binary search tree are swapped, design an algorithm to correct the tree.
Hint: Perform an inorder traversal. At each step verify if we are getting a sorted sequence by inorder traversal. This can be obtained by comparing a number with its successor and predecessor. If the node does not satisfy the constraint, then remember the node. Finally, fix the two nodes which have been swapped.
Q4. Given a Binary Search Tree and two numbers x and y, find the shortest path ( minimum number of hops) between the numbers.
Hint: Perform a simultaneous search for the numbers in the BST. The first node where the search splits is the least common ancestor the numbers. Taking this as reference node, find the depth of each of the nodes from this reference node. Sum of the depths is the length of the shortest path.
Q5. Given two binary search tree, merge these in-place to get a new binary search tree.
Java source code:
Main class: MergeTwoBST.java
Other classes: BinaryTree.java , Node.java , NodeInt.java , NodeStr.java
Input File: UnorderedNumberSequence
Hint: First node is root. Scan the traversal till we get a value greater than the root. Then, the left part forms the left subtree whereas right part forms the right subtree.
Q2. Given a Preorder traversal of a Binary Search Tree, design an algorithm to verify if each non-leaf node has only one children.
Hint: a) If a node has only one children then all its children are greater ( for right subtree) or lesser ( for a left subtree ) than it. IN preorder traversal all the children of a node comes after the node. So, we just need to check if all the nodes are greater or lesser. To do it efficiently, we can use the property that the largest node is the rightmost node whereas the smallest node is the leftmost node.
b) Construct a BST from Preorder traversal. First node is root. Scan the traversal till we get a value greater than the root. Then, the left part forms the left subtree whereas right part forms the right subtree.
Q3. Two nodes in a binary search tree are swapped, design an algorithm to correct the tree.
Hint: Perform an inorder traversal. At each step verify if we are getting a sorted sequence by inorder traversal. This can be obtained by comparing a number with its successor and predecessor. If the node does not satisfy the constraint, then remember the node. Finally, fix the two nodes which have been swapped.
Q4. Given a Binary Search Tree and two numbers x and y, find the shortest path ( minimum number of hops) between the numbers.
Hint: Perform a simultaneous search for the numbers in the BST. The first node where the search splits is the least common ancestor the numbers. Taking this as reference node, find the depth of each of the nodes from this reference node. Sum of the depths is the length of the shortest path.
Q5. Given two binary search tree, merge these in-place to get a new binary search tree.
Java source code:
Main class: MergeTwoBST.java
Other classes: BinaryTree.java , Node.java , NodeInt.java , NodeStr.java
Input File: UnorderedNumberSequence
Q4 Can be done in single scan... it doesnt need to scans of tree.
ReplyDeleteHere is the C code:
int path[100],pathIndex=0,found=-999;
int findShortestElement(int x,int y,struct treeDef *p1)
{
int state=0, state_left, state_right,i;
if(p1 != NULL)
{
if(p1->data == x || p1->data == y)
{
state=1;
path[pathIndex++] = p1->data;
}
state_left=findShortestElement(x,y,p1->left);
if(state_left == 1)
{
path[pathIndex++] = p1->data;
}
state_right=findShortestElement(x,y,p1->right);
if( state_left == 1 && state_right == 1)
{
//this is LCM..
//path[pathIndex++] = p1->data;
printf("Found the complete path\n");
for(i=0;idata;
return 1;
}
else if(state_left == 1)
{
return 1;
}
else
{
return state;
}
}
}