Binary Tree Coding Challenges in JS: Invert a Binary Tree
This week’s problem involves a data structure we previously covered, trees. Please visit the previous article here, to learn more about binary trees and to implement one on your own in JavaScript! A tree consists of interconnected nodes, the main relationship being parent nodes and child nodes. Binary trees are very popular in computer science, it’s a case where parent nodes can have at max 2 child nodes. But there will be cases where ternary or quaternary trees are more appropriate. The important thing to remember is that a tree is a data structure that has a parent-child relationship.
Coding challenges and problems in real life generally revolve around efficiently traversing these trees. If you are unfamiliar with some common graph traversal techniques DFS (Depth First Search) and BFS (Breadth First Search) I would advise you to use this resource to review.
Inverting a Binary Tree
This is a classic problem, ‘Given a root, invert the corresponding binary tree and return the root.’
The outcome we want can be seen in the diagram below:
For this solution, I will be creating a binary tree by connecting nodes. Then I will create a ‘print’ function that also traverses our tree and returns an array of node values. Finally, I will create the invert function that will carry the logic to invert our tree.
The solution to our problem is our invert function. It takes a recursive DFS approach by traversing down the levels of a tree before performing the swap on the way back up. The setup for this problem took a majority of the lines in our code but now you can reuse the code by saving it down on a file or implementing your own class!
When the above snippet is run on your local machine the output should look something like the following:
Thanks for taking the time to go through this problem with me this week! I will be covering many more tree traversal problems in the weeks to come!
