Skip to main content

Manipulate

1008. Construct Binary Search Tree from Preorder Traversal​

Medium·
FIG. CONSTRUCT BST FROM PREORDER● INTERACTIVE
visualization loads as you reach it
Time
O(n²)
  • putIntoTree is called once for each of the n - 1 remaining values, and each call walks from root down to a leaf - up to O(n) steps for a skewed BST (e.g. a strictly ascending or descending preorder) - giving O(n²) overall.
Space
O(n)
  • The constructed tree holds all n nodes (root plus one new_node per value).
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·
2 Approachesclick to switch
FIG. INCREASING ORDER SEARCH TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • recursion performs an in-order visit of every one of the n nodes exactly once.
Space
O(n)
  • A brand-new TreeNode(node.val) is allocated for each of the n values, on top of a recursion call stack of up to h frames (h <= n).
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