Increasing Order Search Tree — LeetCode 897 Python Solution

The problem

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Example

Input

root = [5,3,6,2,4,null,8,1,null,null,null,7,9]

Output

[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Python solution

# 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 increasingBST(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            if root is None:
                return
            nonlocal prev
            dfs(root.left)
            prev.right = root
            root.left = None
            prev = root
            dfs(root.right)

        dummy = prev = TreeNode(right=root)
        dfs(root)
        return dummy.right

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 897. Increasing Order Search Tree is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems