897. Increasing Order Search Tree

Approach 1: In-order tree traversal

We simply store the node values one by one from the tree using the in-order tree traversal and once we are done we can simply generate a tree in the required configuration

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderTraversal(self, root):
"""
https://leetcode.com/problems/binary-tree-inorder-traversal/description/
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right
def increasingBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
l = self.inorderTraversal(root)
rootCopy = TreeNode(l[0])
traverse = rootCopy
for i in l[1:]:
traverse.left = None
traverse.right = TreeNode(i)
traverse = traverse.right
return rootCopy

Time Complexity: O(N) [number of node is N]

Space Complexity: O(N)