[Leetode] 226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/description/

initial

wow i couldnt lol

but we can solve it recursively where we do a postorder traversal all the way to the leaf node. Obviously leaf node's left and right nodes are null, and when nodes are null, we just return out of recursion. Post order means left-> right->node.

So when right leaf node is done being traversed, the result of that traversal is stored temporarily in-memory and not assigned to root.left yet. We go to the left leaf node and traverse that. After that 2 recursions are complete, only then we swap the current root's left and right node with the results that have been stored in-memory.

And very impt. WHY do we need to return root at the end? We need to return root because in recrusion, you need to pass the updated root value down the call stack. So parent nodes will have the updated root value. It is like DFS graph traversal that we did.

Lastly, you need self.method_name if u want to use a method within a class. I explained it here

https://velog.io/@whitehousechef/python-class

solution

from typing import Optional

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return 
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

def printTree(root):
    if root:
        printTree(root.left)
        print(root.val, end=" ")
        printTree(root.right)

# Example usage
if __name__ == "__main__":
    # Create a sample binary tree
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1)
    root.left = TreeNode(2, TreeNode(4), TreeNode(5))
    root.right = TreeNode(3)

    # Print the original tree
    print("Original tree:")
    printTree(root)
    print()

    # Create a Solution instance
    solution = Solution()

    # Invert the tree using the invertTree method
    inverted_root = solution.invertTree(root)

    # Print the inverted tree
    print("Inverted tree:")
    printTree(inverted_root)

revisited may 12th

while you can try and do

def invertTree(root):
    hola = root.left
    root.left=root.right
    root.right=hola

this works only up to depth =1. For depth =2, it is not invereted properly as you can you see in example 1. So you have to invert recursively.

then i tried

def invertTree(root):
    if root==None:
        return
    root.left=invertTree(root.right)
    root.right=invertTree(root.left)

but i get a TreeNode with just root Node and no left and right treeNodes. That is cuz i am not returning anything from this funcion - effectively void in Java. We have to return root after recursion to return and assign the result of invertTree to root.left or root.right.

but even when returning root, look at this recursion and pointer. If root.left is updated with result of invertTree, the next of line of code root.right=invertTree(root.left) takes this new value of root.left as root.left now points to this updated value.

Instead, we should preserve the original pointer, which points to original treeNode objects via

root.left, root.right = invertTree(root.right), invertTree(root.left)

Preservation of Original Pointers:

Despite making recursive calls, the original pointers to the subtrees are preserved. These pointers are not modified during the recursive calls themselves.

Simultaneous Assignment:

Once the recursive calls return, the results (inverted subtrees) are simultaneously assigned back to root.left and root.right. This assignment occurs atomically: both assignments happen at the same time.

both assignments happen at same time so pointers are preserved.

revisited july 5th

you can store the results in temporary variables like

    # Recursively invert the left and right subtrees
    left_inverted = invertTree(root.left)
    right_inverted = invertTree(root.right)
    
    # Swap the left and right subtrees
    root.left = right_inverted
    root.right = left_inverted

complexity

n^2 time cuz therte are 2 options? nope

Time Complexity:
The time complexity is O(n), where n is the number of nodes in the binary tree.

Each node in the tree is visited exactly once during the recursion.
The work done at each node (swapping left and right subtrees) is constant time.

space:
worst is n cuz it can be compeelte unbalanced to one side and BST's space depends on the height of the tree.

best is a balanced BST, in which is log n

Worst Case (Unbalanced Tree):
In the worst-case scenario, the binary tree is completely unbalanced, meaning it is skewed to one side. For example, consider a binary search tree (BST) where each node only has a right child. The tree looks like a linked list with all nodes in a single path.

Height: The height of the tree in this case is equal to the number of nodes (n).
Recursion Depth: Each recursive call goes deeper into the tree, reaching the maximum depth for each node.
Call Stack Usage: The call stack will have a frame for each node in the skewed path.
Space Complexity: Since the height of the tree is O(n) and each node adds a frame to the call stack, the space complexity becomes O(n).
Best Case (Balanced Tree):
In the best-case scenario, the binary tree is perfectly balanced, as is often the case with a well-constructed binary search tree (BST). In a balanced tree, each node has two roughly equal subtrees.

Height: The height of the tree is logarithmic with respect to the number of nodes (log₂(n)).
Recursion Depth: The depth of the recursion is limited by the balanced structure of the tree.
Call Stack Usage: The call stack depth is logarithmic in the number of nodes.
Space Complexity: As the height of the tree is O(log n), the space complexity becomes O(log n).