Mirror Binary Tree Nodes

editor-page-cover

Problem Statement

Given the root node of a binary tree, swap the ‘left’ and ‘right’ children for each node. The below example shows how the mirrored binary tree should look like.

widget

Hint

  • Depth first traversal
  • Bottom up mirroring

Try it yourself

void mirror_tree(BinaryTreeNode* root) {
  //TODO: Write - Your - Code
}

Solution

void mirror_tree(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  // We will do a post-order traversal of the binary tree.

  if (root->left != nullptr) {
    mirror_tree(root->left);
  }

  if (root->right != nullptr) {
    mirror_tree(root->right);
  }

  // Let's swap the left and right nodes at current level.

  BinaryTreeNode* temp = root->left;
  root->left = root->right;
  root->right = temp;
}

int main(int argc, char* argv[]) {

  BinaryTreeNode* root = create_random_BST(15);
  display_level_order(root);
  mirror_tree(root);
  cout << endl << "Mirrored tree = " << endl;
  display_level_order(root);
}

Solution Explanation

Runtime Complexity

Linear, O(n).

Every sub-tree needs to be mirrored so we visit every node once and mirror the sub-tree starting there. Hence run time complexity is O(n).

Memory Complexity

Linear, O(n) in the worst case.


Solution Breakdown

Recursive solution has O(h) memory complexity, for a balanced tree, as it will consume memory on the stack up to the height of the binary tree. For a skewed tree, it can be O(n).

Here, we will do a post order traversal of the binary tree. For every node, we will swap it’s left child with its right child. The original nodes are shown in green color while the nodes that have been swapped are shown in grey. The node at the top of the stack (current node) is shown in light blue. Note that we are doing DFS on the tree i.e. before returning from a node all its children have been visited (and mirrored).