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):
:type root: TreeNode
:rtype: List[int]
res, stack = [], []
while True:
while root:
root = root.left
if not stack:
return res
node = stack.pop()
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)