How to Invert a Binary Tree with DataWeave



 

In this post:

 

The DataWeave language is a simple, powerful tool used to query and transform data inside of Mule.


But you can also use it to solve algorithmic problems.


How to invert a Binary Tree is a popular coding question to test your skills.


Let’s try to solve this with DataWeave.



Definition


Ok, but what is a binary tree? Yes, sure!


Firstly we define a tree as a set of elements (nodes), with the following properties:

  • Each node can be connected to many children

  • Each node has one parent, except the root node that has no parent


A binary tree is a tree where each node has at most 2 children: “left” and “right”.


We can define the DataWeave binary tree structure in the following way:




Problem


In order to invert a binary tree, we need to swap left and right for every level of the tree, as you can see in the following example:




Solution


It's easier than it looks. Thanks to Mr. Recursion!


We can solve the problem for the first children by swapping them and then recursively applying the same solution for the left and right sub-tree.


Input


DataWeave Solution


Output


Note: This solution is using regular recursive functions. If the recursion level exceeds 255 iterations, you will receive a Stack Overflow error. To avoid this, you can also use tail-recursive functions. To learn more about this, see this article.



Conclusion


Now we know how to use Mr. Recursion in DataWeave in order to solve the invert binary tree problem.


Thanks for reading my post and I hope it will help understand this wonderful language.


That’s it for now! See you in the next post!

-Stefano



 

About ProstDev


Our mission is to provide different levels of expertise and knowledge to those that want to keep up with the IT world. Not only you can find information about different technologies, but we also help you to get started in content creation so you can share your knowledge with the rest of the community.


Contact us for more details about contributing.

Read more of our articles.

Meet the team and become a contributor!


187 views1 comment