Manipulate

1008. Construct Binary Search Tree from Preorder Traversal

Medium·

1008Construct Binary Search Tree from Preorder Traversal

Iterative Insertion

O(n²) timeO(1) aux

FIG. CONSTRUCT BST FROM PREORDER● INTERACTIVE

visualization loads as you reach it

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

---

897. Increasing Order Search Tree

Easy·

897Increasing Order Search Tree

2 Approaches

Recursive (Create new tree)

O(n) timeO(h) aux

Recursive (In-place)

O(n) timeO(h) aux

FIG. INCREASING ORDER SEARCH TREE● INTERACTIVE

visualization loads as you reach it

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

---