226. Invert Binary Tree

📝 Problem Details

• Title: 226. Invert Binary Tree
• Link: https://leetcode.com/problems/invert-binary-tree/
• Difficulty: Easy
• Tags/Categories: Trees DFS

💭What Were My Initial Thoughts?

- invert the tree:
	- swap a nodes left child with its right child 

💡 Explanation of Solution

DFS, recursively check the left and right subtrees until we reach a leaf node
- create a temp node and perform the swap of the leaf node's children
- recurse up the call stack until all swaps have been performed

⌛ Complexity Analysis

Time Complexity: O(n)
- DFS traversal visiting each node a single time 

Space Complexity: O(log n) to O(n) depending on balance of the tree due to use of recursive call stack 

💻 Implementation of Solution

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
 
        root->left = invertTree(root->left);
        root->right = invertTree(root->right);
 
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
 
        return root;
    }
};