Recursion and Trees
77 / 170Recursion and TreesLesson 10 of 13About 47 min
One traversal tells you the roots. Another tells you where to split.
For a search tree the ordering already supplies the in-order sequence, so a single pre-order traversal is enough. That makes a good place to see the splitting idea without the index bookkeeping.
def build_from_preorder(values): """Rebuild a search tree from its pre-order sequence.""" if not values: return None root_value = values[0] cut = 1 while cut < len(values) and values[cut] < root_value: cut += 1 # everything smaller belongs on the left return [root_value, build_from_preorder(values[1:cut]), build_from_preorder(values[cut:])] print(build_from_preorder([10, 5, 1, 7, 15]))Preorder visits the root first, so preorder[0] names the root. Finding that value in the inorder list is what splits the remaining nodes into the two subtrees. Type the three lines it prints.
preorder = [3, 9, 20, 15, 7]inorder = [9, 3, 15, 20, 7] root = preorder[0]cut = inorder.index(root) print("root:", root)print("left subtree holds: ", inorder[:cut])print("right subtree holds:", inorder[cut + 1:])Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.