## Saturday, 4 May 2013

### Mirror a binary tree

Introduction

Mirroring a binary tree, a common question nowadays to understand whether the candidate knows about tree traversal. Asking plainly in-order/pre-order is of no use!! :)

Solution

The dummies way is to directly jump to code which never works even for such a simple problem.

First thought, i got this code:

`Tree* mirror(Tree* node)`
`{`
`    if(node == NULL)`
`        return NULL;`
` `
`    node->left = mirror(node->right);`
`    node->right = mirror(node->left);`
` `
`    return node;`
`} `

Flaws in it?

- This is a mugged up code!!

- You didn’t think about whether to output the mirrored tree in a new data structure or to do it in-place

- Why you cannot use tail recursion for in-place,

- Reason 1: you need to swap left & right using a temporary storage. You need to expand the tree on the stack

- Reason 2: The above kind of swapping loses the node->left data whatever magic your recursion does.

Now, we got full of issues, think basic, non-iterative way

`tmp = tree->left;`
`tree->left = tree->right;`
`tree->right = tmp;`

Whatever way you follow, you need to do the above swap.

Corrected code for reproduction of mirrored tree, as a copy

`Tree* mirror(Tree* node)`
`{`
`    if(node == NULL)`
`        return NULL;`
` `
`    Tree *newNode = createNode(node->data);`
`    newNode->left = mirror(node->right);`
`    newNode->right = mirror(node->left);`
` `
`    return newNode;`
`}`

Correct code for creating mirrored tree, in-place

- do a post order traversal to read the full tree into the recursion stack

- do the primitive swap operation

`Tree* mirror(Tree* node)`
`{`
`    if(node == NULL)`
`        return NULL;`
` `
`    mirror(node->left);`
`    mirror(node->right);`
`    Tree *tmp = node->left;`
`    node->left = node->right;`
`    node->right = tmp;`
` `
`    return node;`
`}`