Manipulate Tree

Create

1008. Construct Binary Search Tree from Preorder Traversal (Medium)

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
    def putIntoTree(root, val):
        node = root
        new_node = TreeNode(val)
        while True:
            if node.left and node.val > val:
                node = node.left
            elif node.right:
                node = node.right
            else:
                break
        if node.val > val:
            node.left = new_node
        else:
            node.right = new_node

    if not preorder:
        return None
    root = TreeNode(preorder[0])
    for i in preorder[1:]:
        putIntoTree(root, i)
    return root

---

Convert

897. Increasing Order Search Tree (Easy)

Recursive - Create new treeRecursive - In-place

Python

def increasingBST(self, root: TreeNode) -> TreeNode:
    def recursion(node):
        nonlocal pointer
        if node:
            recursion(node.left) if node.left else None
            pointer.right = TreeNode(node.val)
            pointer = pointer.right
            recursion(node.right) if node.right else None

    new_root = pointer = TreeNode(None)
    recursion(root)
    return new_root.right