CSc 120: Trees
Expected Behavior
Write a recursive function preorder_to_bst(preorder),
where preorder is list of values representing the node values
of the preorder traversal of a binary search tree, and creates and
returns the binary search containing those values.
Your function should work for empty trees, trees with one node, and trees
with many nodes.
Implementation Notes
This problem is very similar to the problem of constructing the
decoding tree for the Huffman assignment. In that problem, you
were given the preorder and inorder traversals of a tree and used those
traversals to create
the new preorder and inorder lists of nodes for the left and right
sides of the tree (recursively).
In this case, you will be able to create a binary
search tree from only the preorder traversal list that is given as an argument.
This is because you can use the property of a binary search tree
to determine which node values will be used for the left side of the tree and which
will be used for the right side of the tree.
Requirements
- You must write a function and not a method.
- Your function must be recursive.
- You may NOT use a list comprehension to make the new preorder lists for the left and right sides of the tree, however you MAY use a loop for this.
Examples
-
Call: preorder_to_bst([3])
Result: "(3 None None)"
-
Call: preorder_to_bst([3, 2, 5])
Result: "(3 (2 None None) (5 None None))"
-
Call: preorder_to_bst([8, 5, 11, 9, 14])
Result: "(8 (5 None None) (11 (9 None None) (14 None None)))"
-
Call: preorder_to_bst([24, 11, 5, 7, 30, 28, 41])
Result: "(24 (11 (5 None (7 None None)) None) (30 (28 None None) (41 None None)))"