pythonrecursionbinary-tree

Is this a top down or bottom up recursion


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.right = left
        root.left = right
        return root

I think its bottom up recursion. As we change the bottom values and proceed to root.


Solution

  • As @matszwecja stated there is no formal CS terminology for this.

    However, if you are referring to these definitions of bottom-up and top-down recursion then it is bottom-up:

    Bottom-up recursion: Processes from the leaves up to the root, performing main computations after reaching the base cases.

    Top-down recursion: Starts processing at the root and may pass information down to child nodes before completing recursive calls.

    Why?

    1. The recursion first goes down to the leaf nodes by calling invertTree on root.left and root.right.
    2. At each leaf (or None node), it starts returning back up the recursive call stack.
    3. Once back at each node, it swaps the left and right children after completing the recursive calls on both sides.