current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite
1

I wrote a small routines to create a mirror for any binary tree. I am just sharing my necessary routines instead of full class. could you please let me know your comments on this. I just curious to find the complexity of this but I am new to algorithms.

void tree_sample::mirror_image()
{
    create_mirror_for_left_subtree(root->left);
    create_mirror_for_right_subtree(root->right);
    tree_node* temp = 0;
    if(root->left)
        temp = root->left;
    root->left = root->right;
    if(temp)
        root->right = temp;
    else
        root->right = NULL;     
}

void tree_sample::create_mirror_for_left_subtree(tree_node *temp)
{
    while(temp!=NULL)
    {
        do_mirror_for_inidividual_node(temp);
        temp = temp->left;
    }
}

void tree_sample::create_mirror_for_right_subtree(tree_node *temp)
{
    while(temp!=NULL)
    {
        do_mirror_for_inidividual_node(temp);
        temp = temp->right;
    }
}

void tree_sample::do_mirror_for_inidividual_node(tree_node *temp)
{
    tree_node* temp2 = 0;
    if(temp->left)
        temp2 = temp->left;
    temp->left = temp->right;
    if(temp2)
        temp->right = temp2;
    else
        temp->right= 0;
}
share|improve this question
up vote 2 down vote

I think you have over complicated things and I don't think it works for the generic tree (as your create_mirror_for_[left|right]_subtree() only recurse down one side of the tree.

Why the test before a swap?

tree_node* temp = 0;
if(root->left)
    temp = root->left;    // If left is NULL you can still assign it 
                          // to temp and get the same result.
root->left = root->right;
if(temp)
    root->right = temp;
else
    root->right = NULL;   // If temp is null you could just assign
                          // it to right then both sides of the branch
                          // are identical and they collapse into a
                          // single statement.

// Much easier to write as:
tree_node* temp = root->left;
root->left      = root->right;
root->right     = temp;

// Which of course can be replaced by std::swap
std::swap(root->left, root->right);

I assume you want to swap all nodes in the tree (otherwise it's not a mirror).

class Tree
{
    public:
        void mirrorTree()
        {
            root.mirrorTree(root);
        }
    private:
        void mirrorTree(Node* node)
        {
            if (node == nullptr) {
                return;
            }
            using std::swap;
            swap(node->left, node->right);
            mirrorTree(node->left);
            mirrorTree(node->right);
        }
};
share|improve this answer
    
Thanks Loki Astari. You are right. I missed to cover the left chileof right subtree and right child of left subtrees. Your code wil cover all the nodes i guess. But is there a way that i can do it in iteration itself rather than using recursion? how can i cover all nodes using loops than being recursive? – funwithlinx May 27 at 4:21
    
@funwithlinx: Yes there is. Look up breadth first traversal of a tree. – Loki Astari May 27 at 14:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.