Invert Binary Tree

 

  1. Clarify the problem:

    • The problem requires inverting a binary tree.
    • Given the root of a binary tree, we need to swap the left and right child of every node.
    • The inversion should be done in-place, meaning we should modify the original tree structure.

  2. Analyze the problem:

    • Input: The root node of a binary tree.
    • Output: The root node of the inverted binary tree.
    • Constraints:
      • The number of nodes in the tree can vary.
      • The binary tree may be empty (root is None).

  3. Design an algorithm:

    • To invert a binary tree, we can traverse the tree in a depth-first manner and swap the left and right child of each node.
    • We can start with the root node and recursively perform the inversion on its left and right subtrees.
    • During the recursive traversal, for each node, we swap its left and right child pointers.
    • The inversion process will continue until we reach the leaf nodes where no further inversion is required.
    • Finally, we return the root node of the inverted binary tree.

  4. Explain your approach:

    • To solve the problem, we will use a recursive approach to perform the inversion in-place.
    • We will define a recursive function, invertTree, that takes a node as input and performs the inversion on its left and right subtrees.
    • The base case of the recursion is when the input node is None, in which case we return None.
    • In the recursive case, we will swap the left and right child pointers of the current node and recursively call the invertTree function on its left and right children.
    • Finally, we return the root node of the inverted binary tree.

  5. Write clean and readable code:

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

def invertTree(root):
    if root is None:
        return None

    # Swap left and right child pointers
    root.left, root.right = root.right, root.left

    # Recursively invert left and right subtrees
    invertTree(root.left)
    invertTree(root.right)

    return root

  1. Test your code:

    • Test Case 1:

      • Create a binary tree with the following structure: 4 /
        2 7 / \ /
        1 3 6 9
      • After inverting the tree, the structure becomes: 4 /
        7 2 / \ /
        9 6 3 1
      • Expected output: Root node of the inverted tree.

    • Test Case 2:

      • Create an empty binary tree.
      • Expected output: None

  2. Optimize if necessary:

    • The provided solution is a standard recursive solution for inverting a binary tree and doesn't require further optimization.

  3. Handle error cases:

    • The code handles the case when the root node is None by returning None, indicating an empty tree.

  4. Discuss complexity analysis:

    • The time complexity of the solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node once during the tree traversal.
    • The space complexity is O(h), where h is the height of the binary tree. In the worst case, when the tree is skewed, the space complexity becomes O(n), as the maximum depth of the call stack will be n. In the average case, the space complexity is O(log n) for a balanced binary tree.
Next Post Previous Post