Recall that a binary search tree is a binary tree with keys at each node such th

Question

Recall that a binary search tree is a binary tree with keys at each node such that for each node with key k, all keys in the left-sub-tree are less than k and all keys in the right-sub-tree are greater than k (assume all keys are unique). The usual in-order traversal produces a key sequence in non-decreasing order. Write an algorithm (give good pseudocode and a complete analysis) that inverts a binary search tree so that for each node with key k, all keys in the left-sub-tree are greater than k and all nodes in the right-sub-tree are less than k. Thus, an in-order traversal of an inverted tree will produce a key ordering in non-increasing order instead. An example of a binary search tree and its inversion is presented in Figure 2. Your algorithm must be efficient and should not create a new tree

Explanation / Answer

Let us define a function ('Invert') with two parameters: The pointer to the current node and the pointer to its parent.

To invert a binary tree rooted at a node N, we just have to do the following:
Invert its left subtree.
Invert its right subtree.
Change one of its child pointers(say left) to its parent.

struct node {
int Value;
struct node* left, *right;
};

void Invert( node* current, node* parent){
if( current== NULL) return;
if( current->left != NULL){
Invert(current->left, current);
current->left=NULL;
}
if( current->right != NULL){
Invert(current->right, current);
current->right=NULL;
}
current->left = parent;
return;
}

int main(){
Invert(root,NULL);/*Call the Invert function with current node as root and its parent as NULL*/
return 0;
}

So, time complexity: O(n), we are traversing each node one time

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.