Invert Binary Tree

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        TreeNode* temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);
        return root;
    }
};

                                            
/**
 * 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 left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        
        root.left = right;
        root.right = left;
        
        return root;
    }
}

                                            
class Solution:
    def invertTree(self, root):
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL){
        return NULL;
    }
    
    struct TreeNode* temp = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(temp);
    
    return root;
}

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

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var invertTree = function(root) {
    if (!root) {
        return null;
    }
    
    const temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    
    return root;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number;
 *     left: TreeNode | null;
 *     right: TreeNode | null;
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val === undefined ? 0 : val);
 *         this.left = (left === undefined ? null : left);
 *         this.right = (right === undefined ? null : right);
 *     }
 * }
 */
function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) {
        return null;
    }
    
    const temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 * }
 */
class Solution {
    
    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function invertTree($root) {
        if ($root === null) {
            return null;
        }
        
        $temp = $root->left;
        $root->left = $this->invertTree($root->right);
        $root->right = $this->invertTree($temp);
        
        return $root;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if root == nil {
            return nil
        }
        
        let left = invertTree(root!.left)
        let right = invertTree(root!.right)
        
        root!.left = right
        root!.right = left
        
        return root
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun invertTree(root: TreeNode?): TreeNode? {
        if (root == null) {
            return null
        }
        
        val left = invertTree(root.left)
        val right = invertTree(root.right)
        
        root.left = right
        root.right = left
        
        return root
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    left := invertTree(root.Left)
    right := invertTree(root.Right)
    
    root.Left = right
    root.Right = left
    
    return root
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def invert_tree(root)
    return nil if root.nil?
    
    temp = root.left
    root.left = invert_tree(root.right)
    root.right = invert_tree(temp)
    
    root
end

                                            
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        match root {
            Some(node) => {
                let left = Solution::invert_tree(node.borrow().left.clone());
                let right = Solution::invert_tree(node.borrow().right.clone());
                node.borrow_mut().left = right;
                node.borrow_mut().right = left;
                Some(node)
            }
            None => None,
        }
    }
}

                                            
%% Definition for a binary tree node.
%%
%% -record(tree_node, {val = 0 :: integer(),
%%                     left = null  :: 'null' | 
invert_tree(null) -> null;
invert_tree(#tree_node{left = Left, right = Right} = Node) ->
    Node#tree_node{left = invert_tree(Right), right = invert_tree(Left)}.

To solve this coding challenge of inverting a binary tree, we need to recursively swap the left and right child nodes of each node in the tree. This process involves traversing the tree, swapping the children at each node, and recursively applying this operation to both subtrees.

# Explanation

A binary tree is a data structure where each node has at most two children referred to as the left child and the right child. Inverting a binary tree means swapping each node's left and right children throughout the entire tree.

Steps Involved:

Base Case : To handle the scenario where the node is
None

(i.e., an empty tree or the leaf node's children), return
None

.
Swap Operation : Swap the left child and the right child of the current node.
Recursive Call : Recursively call the invert function for the (swapped) left subtree and the right subtree.
Return the root : After all swaps and recursive calls are done, return the current node (root of the subtree being processed).

To illustrate the detailed steps, here is a pseudocode with comments for clarity:

Pseudocode

                                            
# Define a function to invert a binary tree given its root node
function invertBinaryTree(node):
# Base case: if the node is None, return None
if node is None:
return None

# Swap the left and right child nodes
temp = node.left   # store the left child in a temporary variable
node.left = node.right  # assign the right child to the left child
node.right = temp  # assign the stored left child to the right child

# Recursively call the function on the left subtree
invertBinaryTree(node.left)

# Recursively call the function on the right subtree
invertBinaryTree(node.right)

# Return the current node (root of the subtree)
return node

Step-by-Step Explanation / Detailed Steps in Pseudocode

Function Definition : The function
invertBinaryTree

takes a single parameter
node

, which represents the root node of the binary tree or subtree.
Base Case Check : Check if the
node

is
None

. If it is, return
None

because a
None

node has no children to swap, and this stops the recursion.
Swapping Children : Use a temporary variable to hold one of the children while swapping to ensure no data is lost. We assign
node.left

to
temp

, then set
node.left

to
node.right

, and finally set
node.right

to
temp

.
Recursive Calls for Subtrees : Call
invertBinaryTree

recursively on
node.left

and
node.right

to ensure that the entire tree is inverted, not just the root node.
Return the Node : Finally, return the node so that the inversion is maintained throughout the recursive calls.

Complexity Analysis

Time Complexity : The function visits each node exactly once; hence, the time complexity is O(n), where n is the number of nodes in the tree.
Space Complexity : The space complexity is O(h), where h is the height of the tree, due to the recursive call stack. In the worst case of a completely unbalanced tree, this could be O(n).

By using this method, you can invert any given binary tree by recursively swapping the children at each node and ensuring the entire structure is properly inverted.