adamcrussell

Inverting a Binary Tree

Suppose we are asked to write a script to invert the tree, by mirroring the children of every node, from left to right, as was the subject of Perl Weekly Challenge 057. How is this done? It turns out the procedure is quite simple and can be expressed quite concisely in terms of a recursion.

  1. invert() the left subtree
  2. invert() the right subtree
  3. swap the left and right subtrees

The code below is based on some previous code, in fact it is virtually identical to that from Graph Visualization (for small graphs) with the addition of an invert() function. Also, the edge labels were added to the graph visualization.

For the full code listing read the GitHub Gist that is linked to.

ch-1.pl
ch-1.pl

The Graph module is useful in that it provides convenient helper functions and allows for easy integration with graph visualization packages such as Graphviz, among others.

Here is the original binary tree, shown using Graphviz.

The original binary tree.
The original binary tree.

And here is the same tree inverted.

Inverted
Inverted




Comments for this post were locked by the author