897.md

Increasing Order Search Tree

Description

link

---

Solution

• See Code

---

Code

Complexity T : O(N) M : O(n)

# 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:
        res = node = TreeNode(0)
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                node.right = TreeNode(root.val)
                node = node.right
                root = root.right

        return res.right