# Invert A Binary Tree (BST)

This is a Rosetta Code post.

### Story

Another popular interview question/assessment is to invert a binary tree. This is where all the left and right children of all non-leaf nodes are interchanged. Think of it as a mirror of the input tree.

This can be visually understood as follows, where 4 is the root node and its subsequent children are inverted.

#### What exactly is a binary tree?

Its simply a data structure

• Used to represent data in a hierarchical format starting from the root node, the subsequent nodes are left/right children nodes
• Every node has 2 components, Data (so its value) and references. These references are either null or a reference to the left/right children
• Adding data to a tree starts at the root node, if its not null the value is added at the root. If the value to be added is LESS than the root its added on the LEFT. If its greater its added on the right. This pattern builds the entire tree and is then performant for searching.

Given the binary tree from the story above, invert it so its values show as the example Output. Its important to remember that its a mirror image so the left and right children are swapped. (Dont try flip it so the root node is at the bottom)

### Solutions

Some of the code below is based on the hilarious Inverting Binary Trees - You Suck at Coding [1] video by Ben Awad. The rest is base on learnings from Data Structures and Algorithms in C#

This would be my pseudocode, I feel its important to try set yourself up for success - pseudocode is part of the journey.

1. Understand what the class will look like
1. There are many ways to do this (see the references at the end) but upfront we need to atleast choose one of
• Iterative - this is when a loop repeatedly executes until the controlling condition becomes false.
• Recursive - this is when a statement in a function calls itself repeatedly.

Recursion is how most of the online examples are doing it so lets roll with that.

1. Ensure you have a base case
1. In the function swap the nodes
1. Call the inversion function with each node