Inverting a binary tree in Java

Recently, I started to practice some LeetCode exercises to improve my algorithm/data structure skills. I can say that the platform provides a good environment to practice and learn with other developers solutions in a several programming languages, discuss, share solutions with others and practice code challenges requested by big companies.

What is LeetCode?

LeetCode is a website that helps candidates to prepare for coding interviews. Users can practice challenges by using the platform's coding and algorithmic problems, alongside with predefined tests for candidate's solution. LeetCode has become a popular resource for technical interviews and coding competitions, alongside with HackerRank.

My routine solving problems

I put myself to the goal of solving at least 3 challenges per day, and my way of thinking in a solution involves my iPad, a pen for screens and the Freeform app. I try to draw and think about the solutions, and this is helping a lot in my code submissions. A lot of challenges sounds hard at first glance, but with a few minutes thinking and architecting the solution (I recommend writing your thinking process). If I can't find the right solution in 30 minutes, then I see the submission from other developers to discover where are my mistakes (sometimes a small step that I forgot in my code). Even if your solution is good enough, I highly recommend looking at other's submissions to think in another ways of solving that problem (some more or less eficient).

The Invert Binary Tree problem

Few days ago I faced the Invert Binary Tree problem at LeetCode, a well-known challenge requested in some interviews and a problem that I saw in when taking a Data Structures/Algorithms classes at the university. Although I never faced this challenge into an interview and haven't ever had explicitly to invert a binary tree in my work, knowing how to invert one gave me more experience with DS, Trees and algorithm thinking and practice some techniques like recursion.
I recommend you to try to solve this problem before reading the rest of this article

The solution

The Invert Binary Tree problem asked me to "Given the root of a binary tree, invert the tree, and return its root." (in other words, we should "mirror" the tree). I used Java programming language to submit a solution, but the steps are the same for other languages (with small syntax changes). The input example and expected output is shown below:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

We are going to use recursion technique to recursively call the invertTree() method, passing some side of the tree as a root. So, as every recursion asks, we need to define a stop condition where the recursion stack will finish and return the respective result of the recursion call. After, we just invert the sides of the tree, assigning to root.left the value returned by the recursion passing root.right as parameter, and do the same to root.right assigning the value of root.left recursion result. As we are modifying the original value, we need an auxiliary variable to store the original result of root.left (you probably implemented a code like this in university and called it swap() method.

At the end we return the root with the nodes inverted. You can check the code below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

Keep in mind that could exist a lot of different solutions for different problems, and that's great. Everyone has a way of thinking and program, Data Structures domain etc. You don't need to follow this exact same code to solve this problem, but you must pay attention to the algorithm complexity (you can use 3 nested for to solve a problem, but this is less performative than using 1 for).

The above is the detailed content of Inverting a binary tree in Java. For more information, please follow other related articles on the PHP Chinese website!