Coding interview Essentials

32. Binary Tree mirroring

Binary Tree mirroring

Introduction

Binary trees are one of the most taught and discussed data structures in computer science courses. A binary tree is a tree-like data structure where each node has at most two children, which we refer to as right and left children. Trees have long been used in computer science as a way to access data stored within nodes that are usually arranged in a particular order intended to make operations like searching for sorting more efficient. Examples of these special types of trees are:

binary search tree,

binary heap

Binary trees are also often used to model data with an inherently bifurcating structure, i.e. where the organization of data into left and right is also part of the information we are representing[^34]. A tree is a recursive data structure because it can be thought of as either being:

  • an empty tree

  • or a node having a binary tree as left and right children.

There are many recursive fundamental algorithms on trees described in the literature that build around this definition, and, as such, recursive solutions to questions about trees are an effective tool in coding interviews. The problem discussed in this chapter focuses on the manipulation of a binary tree into another binary tree so that the latter is a mirror image of the former. As we will see, the question is quite vague as it can be unclear what being a mirror actually means in this context so it is important to ask relevant questions really means and perhaps even create a few examples cases (which we provide later in this chapter) that clarify what the interviewer is expecting.

The tree definition that we will use throughout the chapter is shown in Listing [list:binary_tree_definition].

Listing 1: Definition of the tree data structure using in Chapter \ref{ch:mirror_binary_tree}.

#ifndef TEST_MIRROR_BINARY_TREE_BINARY_TREE
#define TEST_MIRROR_BINARY_TREE_BINARY_TREE

template <typename T>
struct Node
{
  Node() = default;
  Node(const T& val) : payload(val), left(nullptr), right(nullptr){};
  Node *left = nullptr, *right = nullptr;
  T payload{};
};

#endif /* TEST_MIRROR_BINARY_TREE_BINARY_TREE */

Problem statement

Write a function that given a binary tree, return a mirror copy of it.


Given the binary tree shown in Figure 36.1 the function returns a tree like the one in Figure 36.2 [ex:mirro_binary_tree:example1].


Given the binary tree shown in Figure 36.3 the function returns a tree like the one in Figure 36.4 [ex:mirro_binary_tree:example2]


Given the binary tree shown in Figure 36.5 the function returns a tree like the one in Figure 36.6 [ex:mirro_binary_tree:example3]

Figure 1: Input binary tree for the Example [ex:mirro_binary_tree:example1].
Figure 2: Output binary tree for the Example [ex:mirro_binary_tree:example1].
Figure 3: Input binary tree for the Example [ex:mirro_binary_tree:example2].
Figure 4: Output binary tree for the Example [ex:mirro_binary_tree:example2].
Figure 5: Input binary tree for the Example [ex:mirro_binary_tree:example3].
Figure 6: Output binary tree for the Example [ex:mirro_binary_tree:example3].

Discussion

Let’s start our discussion by trying to understand what a mirror copy of a tree really looks like. If we have a tree \(T\) rooted at node \(n\) then its mirror image can be defined as follows:

  • if \(n\) has no children: return \(T\). See Figures 36.7 and 36.8.

  • if \(n\) has one only the left child \(n_l\): return \(T\) having as left child the a mirrored copy of \(n_l\). See Figures 36.11 and 36.12.

  • if \(n\) has one only the left child \(n_r\): return \(T\) having as right child the a mirrored copy of \(n_r\). See Figures 36.9 and 36.10.

  • if \(n\) has both children: return \(T\) having as left child the mirrored copy of its right child \(n_r\) and, as right child the mirrored copy of its left child \(n_l\). See Figures 36.13 and 36.14. Another example of this case can be found in the node \(5\) in the Example [ex:mirro_binary_tree:example1] where its left and right children are first mirrored individually and then swapped.

This recursive definition can be refined into the following simple idea: In order to create the mirror image of a tree \(T\) rooted at \(n\) we first mirror its children individually and only after do we swap them. Given that we can turn a tree into its mirror image all that is necessary is to first create a copy of the origin tree and then mirror it (remember that the problem is asking to return a copy). Listing [list:mirror_binary_tree1] shows a recursive implementation of this idea.

Listing 2: Solution to the problem of creating a mirror of a binary tree. Works by first creating a copy of the original tree and only then performing the mirroring.

#include "binary_tree.h"

template <typename T>
Node<T>* copy_binary_tree(const Node<T>* const root)
{
  if (!root)
    return nullptr;

  auto root_copy   = new Node<T>(root->payload);
  root_copy->left  = copy_binary_tree(root->left);
  root_copy->right = copy_binary_tree(root->right);
  return root_copy;
}

template <typename T>
void mirror_binary_tree_in_place(Node<T>* const node)
{
  using std::swap;

  if (!node)
    return;

  mirror_binary_tree_in_place(node->left);
  mirror_binary_tree_in_place(node->right);
  swap(node->left, node->right);
}

template <typename T>
Node<T>* mirror_binary_tree(const Node<T>* const root)
{
  auto&& tree_copy = copy_binary_tree(root);
  mirror_binary_tree_in_place(tree_copy);
  return tree_copy;
}

The complexity of the code above is \(O(n)\) where \(n\) is the number of nodes in \(T\). However, despite the fact that splitting the copying and the mirroring steps simplifies the reasoning and the implementation this is not optimal as we need to traverse the whole tree twice. We can create the copy on the fly as we visit \(T\) as shown in Listing [list:mirror_binary_tree2]. This approach does not lower the asymptotic complexity but it effectively means that we only need to traverse the original tree once instead of twice.

Listing 3: Solution to the problem of creating a mirror of a binary tree. The copy and the mirroring are performed simultaneously while visiting $T$.

template <typename T>
Node<T>* mirror_binary_tree_on_the_fly(Node<T>* const node)
{
  if (!node)
    return nullptr;

  auto root_mirror   = new Node<T>(node->payload);
  root_mirror->right = mirror_binary_tree_on_the_fly(node->left);
  root_mirror->left  = mirror_binary_tree_on_the_fly(node->right);
  return root_mirror;
}
Figure 7: Example of single node tree.
Figure 8: Mirror image of the tree in Figure 36.7.
Figure 9: Example of node with a single child: the right one.
Figure 10: Mirror image of the tree in Figure 36.9.
Figure 11: Example of node with a single child: the left one.
Figure 12: Mirror image of the tree in Figure 36.9.
Figure 13: Example of node with a single child: the left one.
Figure 14: Mirror image of the tree in Figure 36.13.