4
      /   \
     2     5
    / \
   1   3

left subtree of 4:  {1, 2, 3}  all < 4
right subtree of 4: {5}        all > 4

DFS in-order visit: 1 → 2 → 3 → 4 → 5

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:

        # Key Insight:
        # - array is already sorted, so an in order traversal of the BST
        #   we build must reproduce this exact array
        # - to guarantee the tree is HEIGHT BALANCED (required by the problem),
        #   always pick the MIDDLE element of the current range as the root
        #   - this splits remaining elements as evenly as possible into
        #     left/right subtrees every time, keeping height O(log n)
        # - elements left of the middle (smaller values) become the left
        #   subtree, elements right of the middle (larger values) become
        #   the right subtree

        # nums = [1, 2, 3, 4, 5], mid index = 2 (value 3)
        #
        #             3
        #           /   \
        #          1     5
        #           \   /
        #            2 4  <- wait, corrected below
        #
        #   left range:  [1, 2]   -> mid index 0 (value 1), 2 becomes right child
        #   right range: [4, 5]   -> mid index 0 (value 4), 5 becomes right child
        #
        #             3
        #           /   \
        #          1     4
        #           \     \
        #            2     5

        def buildBST(left, right):

            # Empty Range:
            #   - no elements available, no node to build
            if left > right:
                return None

            # Pick Middle as Root:
            #   - guarantees balanced split of remaining elements
            mid = (left + right) // 2

            root = TreeNode(nums[mid])

            # Elements left of mid form the left subtree
            root.left = buildBST(left, mid - 1)

            # Elements right of mid form the right subtree
            root.right = buildBST(mid + 1, right)

            return root

        # Start search across the full array
        newBst = buildBST(0, len(nums) - 1)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return newBst

Sol 1: DFS Pre Order Recursive Passing Range Limits
1. dfs(node, low, high):
   a. if not node: return True
   b. if not (low < node.val < high): return False
   c. left_valid = dfs(node.left, low, node.val)
   d. right_valid = dfs(node.right, node.val, high)
   e. return left_valid and right_valid
2. return dfs(root, -inf, inf)

Sol 2: BFS Pre Order Iterative Passing Queuing Range Limits
1. queue = deque([(root, -inf, inf)])
2. while queue:
   a. (node, low, high) = queue.popleft()
   b. if not node: continue
   c. if not (low < node.val < high): Return False
   d. queue.append((node.left, low, node.val))
   e. queue.append((node.right, node.val, high))
3. return True

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        # BST Property: (left -> root -> right)
        #   - start with lax boundaries [-inf, inf]
        #   - keep tightening bounds as we encounter nodes
        #   - Node.left =  [sameLeft, node.val]
        #   - Node.right = [node.val, sameRight]

        def dfs(node, low, high):

            # Empty Case:
            # leaf will always be valid
            if node == None:
                return True

            # Validate Node:
            #   - if node touches or is outside boundary, tree is invalid
            if node.val <= low:
                return False
            elif high <= node.val:
                return False

            # Tighten bounds for left subtree
            #   - [sameLeft, node.val]
            leftSubtreeValid = dfs(node.left, low, node.val)
            
            # Tighten bounds for right subtree
            #   - [node.val, sameRight]
            rightSubtreeValid = dfs(node.right, node.val, high)

            # Return if nodes subtrees are also valid
            return leftSubtreeValid and rightSubtreeValid

        # Start with infinite bounds
        treeValid = dfs(root, float('-inf'), float('inf'))

        # overall: tc O(n)
        # overall: sc O(h) for balanced / O(n) for skewed trees
        return treeValid

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # BST Property: (left -> root -> right)
        #   - start with lax boundaries [-inf, inf]
        #   - keep tightening bounds as we encounter nodes
        #   - Node.left =  [sameLeft, node.val]
        #   - Node.right = [node.val, sameRight]

        # Iterate queue
        queue = deque([(root, float('-inf'), float('inf'))])

        while queue:

            # Grab current node boundaries
            node, low, high = queue.popleft()

            # Empty Case:
            # leaf is always valid
            if node == None:
                continue

            # Validate Node:
            #   - if node touches or is outside boundary, tree is invalid
            if node.val <= low:
                return False
            elif high <= node.val:
                return False

            # Pass down new boundaries to left subtree
            #   - [sameLeft, node.val]
            queue.append((node.left, low, node.val))

            # Pass down new boundaries to right subtree
            #   - [node.val, sameRight]
            queue.append((node.right, node.val, high))

        # No subtree returned invalid, entire tree is valid

        # overall: tc O(n)
        # overall: sc O(h) for balanced / O(n) for skewed trees
        return True

Sol 1: DFS Pruning Optimization
1. if not root: return None
2. if root.val < low:
    return trimBST(root.right, low, high)
3. if root.val > high:
    return trimBST(root.left, low, high)
4. root.left = trimBST(root.left, low, high)
5. root.right = trimBST(root.right, low, high)
6. return root

    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        
        # BST Property: (left < root < right)
        #   - if we encounter a node outside the valid boundaries,
        #     we can trim their entire subtree
        
        def dfs(node, low, high):

            # Empty Case:
            # found leaf, nothing to remove
            if node == None:
                return None

            # Node outside left boundaries:
            #   - node and left subtree, both are guaranteed to be out of bounds
            #   - replace node with a trimmed right subtree, may still have in bound nodes
            if node.val < low:
                return dfs(node.right, low, high)

            # Node outside right boundaries:
            #   - node and right subtree, both are guaranteed to be out of bounds
            #   - replace node with a trimmed left subtree, may still have in bound nodes
            if high < node.val:
                return dfs(node.left, low, high)

            # Node is within both boundaries
            #   - trim left and right subtrees
            node.left = dfs(node.left, low, high)
            node.right = dfs(node.right, low, high)

            # Tree has been trimmed, return valid node and its subtrees if any
            return node

        # Trim starting at root
        newRoot = dfs(root, low, high)

        # overall: O(n)
        # overall: O(log(n)) for balanced / O(n) for skewed
        return newRoot

Sol 1: Recursive BST Traversal
1. if p.val < root.val and q.val < root.val:
    return lowestCommonAncestor(root.left, p, q)
2. elif p.val > root.val and q.val > root.val:
    return lowestCommonAncestor(root.right, p, q)
3. else:
    return root

Sol 2: Iterative BST Traversal
1. node = root
2. while node:
   a. if p.val < node.val and q.val < node.val:
        node = node.left
   b. elif p.val > node.val and q.val > node.val:
        node = node.right
   c. else:
        return node

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    

        def dfs(node, p, q):

            # Lowest Common Ancestor:
            # First node to contain p and q in left and right subtree

            # BST Property: (left < node < right)
            #   - the first time that p and q split into different subtrees,
            #       that node will be the lowest common ancestor

            # Both vals are smaller:
            #   - both vals live in the left subtree, explore
            if p.val < node.val and q.val < node.val:
                return dfs(node.left, p, q)

            # Both vals are larger:
            #   - both vals live in the right subtree, explore
            elif p.val > node.val and q.val > node.val:
                return dfs(node.right, p, q)

            # Vals Split Between Subtrees:
            #   - one val is larger than curr, one val is smaller
            #   - curr node is the lowest common ancestor
            return node

        lca = dfs(root, p, q)

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return lca

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Lowest Common Ancestor:
        # First node to contain p and q in left and right subtree

        # BST Property:
        # - given that (left < root < right)
        # - the first time that p and q split,
        #   is the node that contains both of them 

        curr = root

        # Traverse until LCA is found
        while curr:

            # Both vals are smaller:
            #   - both vals live in the left subtree, explore
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left

            # Both vals are larger:
            #   - both vals live in the right subtree, explore
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right

            # One val is larger, one val is smaller:
            #   - vals are split between the different subtrees
            #   - curr node is the lowest common ancestor
            else:
                break

        lca = curr

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(1)
        return lca

Sol 1: Recursive Traversal
1. if root == None:
    return TreeNode(val)
2. if val < root.val:
    root.left = insertIntoBST(root.left, val)
3. else:
    root.right = insertIntoBST(root.right, val)
4. return root

Sol 2: Iterative Traversal
1. if not root: return TreeNode(val)
2. current = root
3. while True:
   a. if val < current.val:
      if current.left: current = current.left
      else: current.left = TreeNode(val); break
   b. else:
      if current.right: current = current.right
      else: current.right = TreeNode(val); break
4. return root

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:

        # BST Property: (left < root < right)

        def dfs(node, val):
            
            # Base Case: 
            #   - explored down bst and reached leaf 
            #   - new val will replace this leaf
            if node == None:
                return TreeNode(val)
            
            # Val is lower:
            #   - val lives in left subtree, explore
            if val < node.val:
                node.left = dfs(node.left, val)

            # Val is greater:
            #   - val lives in right subtree, explore
            else:
                node.right = dfs(node.right, val)

            return node
        
        # Insert
        newRoot = dfs(root, val)

        # tc: O(h)
        # sc: O(log n) for balanced / O(n) for unbalanced tree
        return newRoot

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        
        # BST Property: (left < root < right)

        # Empty Case:
        # tree is empty, new node becomes root
        if not root:
            return TreeNode(val)
        
        curr = root
        
        while True:

            # Val is lower:
            #   - val lives in left subtree, explore
            if val < curr.val:
                
                # Left node exists, continue exploring
                if curr.left:
                    curr = curr.left

                # Base Case: 
                #   - explored down bst and reached leaf 
                #   - new val will replace this leaf
                else:
                    curr.left = TreeNode(val)
                    break

            # Val is greater:
            #   - val lives in right subtree, explore
            else:

                # Right node exists, continue exploring
                if curr.right:
                    curr = curr.right
                
                # Base Case: 
                #   - explored down bst and reached leaf 
                #   - new val will replace this leaf
                else:
                    curr.right = TreeNode(val)
                    break
        
        # Return original root to maintain BST structure

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(1) 
        return root

Sol 1: DFS In Order Recursive Early Stop with Global Element Counter
1. (result = None)
2. inorder(node):
   a. if not node or result is not None: return
   b. inorder(node.left)
   c. k -= 1
   d. if k == 0:
        result = node.val
        return
   e. inorder(node.right)
3. inorder(root)
4. return result

Sol 2: DFS In Order Iterative with Element Counter
1. stack = []
2. while True:
   a. while root:
        stack.append(root)
        root = root.left
   b. root = stack.pop()
   c. k -= 1
   d. if k == 0: Return root.val
   e. root = root.right

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        
        # BST property:
        # in order traversal (left -> root -> right) visits nodes
        # in strictly ascending order

        # K Nodes Counter:
        # - counts down remaining nodes until kth smallest reached
        kCount = k
        
        def inorder(node):

            nonlocal kCount

            # Empty Case:
            #   - empty subtree, nothing to find here
            if node == None:
                return None
            
            # Find the kth smallest:
            #   - in order iteration gives you the next smallest
            #   - capture the result so it can propagate back up
            leftRes = inorder(node.left)

            # Early Stop:
            #   - answer already found in left subtree, propagate it up
            if leftRes != None:
                return leftRes

            # Decrement node count
            kCount -= 1

            # If reached kth smallest:
            #   - return directly
            if kCount == 0:
                return node.val
            
            # Ran out of smaller left, current node wasn't answer either:
            #   - continue with larger right values
            #   - propagate whatever the right subtree finds (or None)
            return inorder(node.right)

        # Smallest
        kthSmallest = inorder(root)
        
        # Start search from root
        # overall: tc O(h + k) average, O(n) worst case (skewed tree, large k)
        # overall: sc O(h) for balanced / O(n) for skewed trees (recursion stack)
        return kthSmallest

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # BST property:
        # in order traversal (left -> root -> right) visits nodes
        # in strictly ascending order

        # Iterative stack
        stack = []
        
        while True:

            # Queue as many small nodes as possible
            while root:
                stack.append(root)
                root = root.left
            
            # Queue:
            #   - pop smallest unvisited node
            root = stack.pop()

            # Decrease node counter
            k -= 1

            # If kth node, return
            if k == 0:
                return root.val
            
            # Ran out of smaller left, move to right subtree
            root = root.right

        # Empty Case:
        # k was larger than the number of nodes in the tree

        # overall: tc
        # overall: sc
        return None

  oh! pseudocode hasn't been written yet, try another card! :)

    def recoverTree(self, root: Optional[TreeNode]) -> None:

        # BST property:
        # in order traversal (left -> root -> right) visits nodes
        # in strictly ascending order

        # 2 Swaps:
        # - will cause either 1 or 2 violations 
        # - a violation being a node that breaks the strictly ascending order
        #   by having value smaller than the node before it

        # ------------------------------------
        # 1 Violation:
        # index:      0   1   2   3   4
        # swapped:    1   2   4   3   5         
        #                         ^    
        #                       (violation, i=3: 4 > 3)     

        # 2 Violations:
        # index:      0   1   2   3   4
        # value:      1   4   3   2   5
        #                     ^   ^
        #                   (violation, i=2: 4 > 3)     
        #                       (violation, i=3, 3 > 2)


        # ------------------------------------
        # Tracking Swaps:

        # 1 Violations (adjacent swap):
        
        # value:   1   2   4   3   5
        #                  ^   ^
        #               prev1 curr1  <- violation #1: 3 < 4
        #                  ^   ^                       prev(4) is 1st swap
        #              first   second                  curr(3) is 2nd swap

        # 2 Violations (non adjacent swap):
        
        # value:   1   4   3   2   5
        #              ^   ^
        #            prev1 curr1        <- violation #1: 3 < 4
        #              ^                                 prev(4) is 1st swap
        #           first
        #                  ^   ^
        #               prev2 curr2     <- violation #2: 2 < 3
        #                      ^                         curr(2) is 2nd swap
        #                     second

        #  First is updated to prev
        #  Second is updated to curr

        # If there is 1 violation:
        #   - first is updated once, ending at prev1
        #   - second is updated once, ending at curr1

        # If there are 2 violations:
        #   - first is updated once, ending at prev1
        #   - second is updated twice, ending at curr2

        # Both cases lead to first and second pointing to the correct values to swap

        # Violation Counter:
        # - tracks how many violations found so far (max 2)
        violations = 0

        # Two values to swap 
        first = None
        second = None

        # Node before violation
        prev = None

        def dfs(curr):

            nonlocal first, second, prev, violations

            # Empty Check / Early Stop:
            #   - empty subtree
            #   - both violations already found, rest of tree is guaranteed sorted
            if not curr or violations == 2:
                return

            # In order traversal
            dfs(curr.left)

            # Early Stop:
            #   - left subtree traversal may have just found the 2nd violation
            #   - stop before doing any more work at this node
            if violations == 2:
                return

            # Strictly ascending broken:
            #   - curr is smaller than prev:
            #   - violation found, track prev and curr in first and second
            if prev and curr.val < prev.val:

                # Updated first to prev1
                if first == None:
                    first = prev

                # Update second to curr1, then to curr2
                second = curr

                # 2nd violation found, no need to go further right
                if violations == 2:
                    return

            # Update prev to curr before we iterate
            prev = curr

            # In order traversal
            dfs(curr.right)

        # Start search at root
        dfs(root)

        # Swap the values to avoid altering tree structure:
        first.val, second.val = second.val, first.val

        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed
        return

    def recoverTree(self, root: Optional[TreeNode]) -> None:

        # BST property:
        # in order traversal (left -> root -> right) visits nodes
        # in strictly ascending order

        # Morris In Order Traversal: (left -> root -> right), O(1) space
        #   - avoids a recursion stack or an explicit stack 
        #     by temporarily threading the tree, 
        #     by using each node's unused right pointer to point back to its in order successor


        # Two values to swap
        first = second = None

        # Node before violation
        prev = None

        curr = root

        # Violation Counter:
        # - tracks how many violations found so far (max 2)
        violations = 0

        # Each edge is threaded and unthreaded at most once
        while curr:

            # No Left Subtree Exists: (____ -> root -> right)
            #   - in order traversal is simple in this case,
            #     just process root and iterate to the right
            #
            #        4
            #         \
            #          5
            #
            if not curr.left:

                # Process Root by:
                #   - First to prev1 and Second to curr1 to curr2 logic
                if prev and curr.val < prev.val:
                    violations += 1
                    if first == None:
                        first = prev
                    second = curr

                # Iterate prev and curr
                prev = curr
                curr = curr.right

                # Early Stop:
                #   - tree is clean here (no thread was touched), safe to stop
                if violations == 2:
                    break


            # Left Subtree Exists: (left -> root -> right)
            #   - in order traversal is not simple in this case
            #   - find the rightmost in the left subtree,
            #     and thread it to current to allow for in order traversal (right -> root) eventually
            #
            #        4
            #       / \
            #      2   5
            #     / \
            #    1   3 - -
            #             - - (thread) - - > 4
            else:

                # Thread
                #   - grab rightmost of the left subtree
                currLeftSubtreeRightmost = curr.left
                while currLeftSubtreeRightmost.right and currLeftSubtreeRightmost.right != curr:
                    currLeftSubtreeRightmost = currLeftSubtreeRightmost.right

                # Thread has not been placed yet:
                #   - place thread from rightmost of left subtree to the root
                if currLeftSubtreeRightmost.right == None:

                    # Place 
                    currLeftSubtreeRightmost.right = curr

                    # Thread placed, ready to explore curr.left
                    #   - due to in order, eventually, the last node we will hit is
                    #     the rightmost of the left subtree,
                    #     at which point the thread will allow us to return to the root
                    curr = curr.left

                # Thread has already been placed:
                #   - in order has brought us to the root, via the thread
                else:

                    
                    # currLeftSubtreeRightmost.right holds the thread that got us here
                    #   - remove the thread
                    currLeftSubtreeRightmost.right = None

                    # Process Root by:
                    #   - First to prev1 and Second to curr1 to curr2 logic
                    if prev and curr.val < prev.val:
                        violations += 1
                        if first == None:
                            first = prev
                        second = curr

                    # Iterate prev and curr
                    prev = curr
                    curr = curr.right

                    # Early Stop:
                    #   - thread was just removed, tree is clean here, safe to stop
                    if violations == 2:
                        break

        # Swap the values to avoid altering tree structure:
        first.val, second.val = second.val, first.val

        # overall: tc O(n)
        # overall: sc O(1)
        return

Sol 1: Recursive Traversal
1. if root == None: return None
2. if key < root.val:
    root.left = deleteNode(root.left, key)
3. elif key > root.val:
    root.right = deleteNode(root.right, key)
4. else:
   a. if root.left == None and root.right == None:
        Return None
   b. elif root.left == None:
        Return root.right
   c. elif root.right == None:
        Return root.left
   d. else:
        successor = root.right
        while successor.left: successor = successor.left
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)
5. return root

Sol 2: Iterative Traversal
1. if not root: return None
2. dummyHead = TreeNode(0), dummyHead.left = root
3. parent = dummyHead
4. current = root
5. (is_left_child = True)
6. while current and current.val != key:
   a. parent = current
   b. if key < current.val:
        current = current.left, is_left_child = True
   c. else:
        current = current.right, is_left_child = False
7. if not current: return root
8. if current.left and current.right:
   a. successor_parent = current, successor = current.right
   b. while successor.left: successor_parent = successor, successor = successor.left
   c. current.val = successor.val
   d. parent = successor_parent, current = successor
   e. is_left_child = (successor_parent.left == successor)
9. child = current.left if current.left else current.right
10. if is_left_child: parent.left = child
11. else: parent.right = child
12. return dummyHead.left

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        
        # BST property: (left < node.val < right)
        
        # BST Deletion:
        
        # 0 or 1 children:
        #   - remove lone node
        #   - replace removed node with child

        # 2 children:
        #       - find in order successor (smallest node in right subtree)
        #       - replace node value with successor
        #       - replacing node temporarily creates 2 successor nodes
        #       - delete original successor node recursively

        def dfs(node, key):

            # Traverse until we find the target node

            # Empty Case: 
            # Target node does not exist
            if node == None:
                return None

            # Target lives in left subtree:
            #    - explore         
            if key < node.val:
                node.left = dfs(node.left, key)
            
            # Target lives in right subtree:
            #   - explore
            elif key > node.val:
                node.right = dfs(node.right, key)
            
            # Found target:
            #   - choose between the 0, 1, or 2 children cases
            else:

                # 0 Children
                #   - remove node
                if node.left == None and node.right == None:
                    return None

                # 1 Child
                #   - replace removed node with child
                elif node.left == None:
                    return node.right

                # 1 Child
                #   - replace removed node with child
                elif node.right == None:
                    return node.left

                # 2 children:
                #       - find in order successor (smallest node in right subtree)
                #       - replace node value with successor
                #       - replacing node temporarily creates 2 successor nodes
                #       - delete original successor node recursively
                else:

                    # Grab right subtree
                    rightSubtree = node.right

                    # Grab smallest node in right subtree
                    #   - traverse left as far as possible
                    smallestNodeInRightSubtree = rightSubtree
                    while smallestNodeInRightSubtree.left:
                        smallestNodeInRightSubtree = smallestNodeInRightSubtree.left
                    
                    # Replace target node with smallest node we just grabbed
                    #   - now there are 2 copies of the smallest node
                    node.val = smallestNodeInRightSubtree.val
                    
                    # Remove original copy of smallest node in right subtree
                    node.right = dfs(rightSubtree, smallestNodeInRightSubtree.val)
                     
            # Original node object either holds:
            #   - some new smallest node
            #   - original value it started with
            return node

        newRoot = dfs(root, key)

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return newRoot

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:

        # BST property: 
        # left < node.val < right
        
        # BST Deletion:
        
        # 0 or 1 children:
        #   - remove lone node
        #   - replace removed node with child

        # 2 children:

        #       a. find in order successor (smallest node in right subtree)
        #       b. replace node value with successor
        #       c. delete successor node iteratively

        # Empty Case: 
        # Target node does not exist
        if root == None:
            return None

        # Dummy head:
        #   - simplifies edge case where root itself is deleted
        #   - dummyHead.left always points to the current tree root
        dummyHead = TreeNode(-1)
        dummyHead.left = root

        # Parent pointer:
        #   - tracks parent of current node so we can relink after deletion
        parentOfCurr = dummyHead

        # Traversal pointer
        curr = root

        # Tracks whether current is the left or right child of parent
        #   - needed to correctly relink after deletion
        #   - helps validate between the 3 cases
        isLeftChild = True

        # Traverse until we find the target node
        while curr and curr.val != key:

            # Target lives in left subtree:
            #    - explore
            if key < curr.val:
                parentOfCurr = curr
                curr = curr.left
                isLeftChild = True

            # Target lives in right subtree:
            #   - explore
            else:
                parentOfCurr = curr
                curr = curr.right
                isLeftChild = False

        # Empty Case:
        # Target node does not exist
        if curr == None:
            return root

        # Found target:
        #   - check the children cases
        #   - replace


        # 2 Children:
        #   - find in order successor (smallest node in right subtree)
        #   - replace node value with successor
        #   - relink pointers so we now target the successor node for removal
        if curr.left and curr.right:

            # Track parent of current smallest for removal
            parentOfSmallestNodeRightSubtree = curr

            # Grab right subtree
            smallestNodeRightSubtree = curr.right

            # Grab the smallest node:
            #   - traverse left as far as possible
            # tc O(log n) for balanced / O(n) for skewed trees
            while smallestNodeRightSubtree.left:

                # Grab parent
                parentOfSmallestNodeRightSubtree = smallestNodeRightSubtree

                # Grab smaller
                smallestNodeRightSubtree = smallestNodeRightSubtree.left

            # Replace target value with smallest node
            curr.val = smallestNodeRightSubtree.val

            # Now there are two copies of the smallest node:
            #   - smallest node will always have 0 or 1 children only
            #   - reset parentOfCurr to parent of smallest
            #   - reset curr to be at smallest
            #   - replace both
            parentOfCurr = parentOfSmallestNodeRightSubtree
            curr = smallestNodeRightSubtree
            isLeftChild = (parentOfSmallestNodeRightSubtree.left == smallestNodeRightSubtree)

        # Curr is either handling the original target,
        # or the smallestNode we just moved

        # 0 or 1 Child:
        if curr.left:

            # Left child exists:
            #   - it's the only child, grab it
            child = curr.left

        else:

            # Right child exists:
            #   - it's the only child, grab it
            child = curr.right

        # Replace parent with child
        if isLeftChild:
            parentOfCurr.left = child
        else:
            parentOfCurr.right = child

        # Dummy head's left holds the head, either:
        #   - the original root
        #   - a new root, if the original root was the node deleted
        newHead = dummyHead.left

        # overall: tc O(log n) for balanced / O(n) for skewed trees
        # overall: sc O(1)
        return newHead

    def numTrees(self, n: int) -> int:

        dp = [0] * (n + 1)

        # Base Case:
        #   - 0 nodes has exactly 1 shape: the empty tree
        dp[0] = 1

        # Pick Tree Size:
        #   - for 1 to n, try every size
        for numNodes in range(1, n+1):

            # Pick Root Node:
            #   - for node 1 to numNodes, pick which one will serve as root
            for rootNode in range(1, numNodes+1):

                # Generate total possible number of trees for this combination of:
                #   - total number of numNodes
                #   - rootNode

                # Count:
                #   - [left ... root ... right]
                #   - left subtree gets [1 ... rootNode-1] or rootNode-1 nodes
                #   - right subtree gets [rootNode+1 ... numNodes] or numNodes-rootNode nodes

                #   - multiply the independently computed counts together:
                #       every possible left shape * every possible right shape

                #   - which means the same as:
                #       total possible combinations for i nodes *
                #       total possible combinations for j nodes

                #   - which is what allows us to use dp
                dp[numNodes] += dp[rootNode - 1] * dp[numNodes - rootNode]

        # Grab combinations
        totalCombinationsForTreeWithNNodes = dp[n]

        # overall: tc O(n^2)
        # overall: sc O(n)
        return totalCombinationsForTreeWithNNodes

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:

        # Notes:
        # - for a range of values [left, right], pick each value rootNode in
        #   that range as the root
        # - values smaller than rootNode (left..rootNode-1) form the left
        #   subtree, values larger than rootNode (rootNode+1..right) form the
        #   right subtree
        # - every combination of (a left subtree shape, a right subtree shape)
        #   produces one distinct valid tree rooted at rootNode

        # Count:
        #   - [left ... root ... right]
        #   - left subtree gets [left ... rootNode-1] nodes
        #   - right subtree gets [rootNode+1 ... right] nodes

        #   - pair every possible left shape with every possible right shape:
        #       every possible left shape * every possible right shape

        #   - which means the same as:
        #       total possible combinations for the left range *
        #       total possible combinations for the right range

        #   - which is what allows us to memoize on (left, right)

        # Number of trees:
        #   - (O(Catalan(n) * n) - Catalan(n)) trees are built
        #   - each tree has O(n) nodes to assemble 
        #   - memoization avoids rebuilding identical shaped ranges,
        #     but each distinct (left, right) range still does real work once
        #   - O(Catalan(n) * n) space to store all generated trees dominates the O(n) recursion stack

        # Range [1, 3], root = rootNode = 2
        #
        #        2
        #       / \
        #      1   3
        #
        #   left subtree built from range [1, 1]
        #   right subtree built from range [3, 3]

        # Base Case:
        #   - empty range (left > right) has exactly 1 valid "shape": None
        #   - MUST return [None], not [], so the cartesian product loop below
        #     still runs once (pairs with the other side's real subtrees)

        # Memoization:
        #   - the values within a range (e.g. [3, 5]) are just consecutive
        #     integers, so the SHAPES of trees buildable from any range of
        #     the same length are structurally identical regardless of the
        #     actual starting value
        #   - memoize on (left, right) so we don't rebuild identical-shaped
        #     subtrees for different recursive calls that hit the same range
        memo = {}

        def buildTrees(left, right):

            # Empty Range:
            #   - no values available, only valid tree is an empty one
            if left > right:
                return [None]

            # Already Computed:
            #   - this exact range has been built before, reuse it
            if (left, right) in memo:
                return memo[(left, right)]

            # All Trees Built From This Range:
            allTrees = []

            # Try every value rootNode in [left, right] as the root
            for rootNode in range(left, right + 1):

                # Build every possible left subtree (values left..rootNode-1)
                leftSubtrees = buildTrees(left, rootNode - 1)

                # Build every possible right subtree (values rootNode+1..right)
                rightSubtrees = buildTrees(rootNode + 1, right)

                # Cartesian Product:
                #   - pair every left shape with every right shape,
                #     each pairing is a distinct valid tree rooted at rootNode
                for leftTree in leftSubtrees:
                    for rightTree in rightSubtrees:
                        root = TreeNode(rootNode)
                        root.left = leftTree
                        root.right = rightTree
                        allTrees.append(root)

            # Cache and return
            memo[(left, right)] = allTrees
            return allTrees

        # Start search across the full range of values
        allBstTrees = buildTrees(1, n)

        # overall: tc O(Catalan(n) * n) - Catalan(n) 
        # overall: sc O(Catalan(n) * n) 
        return allBstTrees