This post is part of the Algorithms Problem Solving series.
This is the Construct Binary Search Tree from Preorder Traversal problem. The description looks like this:
Return the root node of a binary search tree that matches the given
(Recall that a binary search tree is a binary tree where for every node, any descendant of
node.left has a value
node.val, and any descendant of
node.right has a value
node.val. Also recall that a preorder traversal displays the value of the
node first, then traverses
node.left, then traverses
It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
My idea was to build the root node with the first element of the list. Then iterate through the list from the index 1 to the last element of the list. For each item, I call helper to insert into the binary search tree.
The helper just follow the rules of insertion in a binary search tree:
- if value is smaller than the current node's value, go to the left
- if value is greater than the current node's value, go to the right
- Always look if the current node has a child. If it has, recursively call the helper passing the child.
- Otherwise, you can insert a new tree node with the new value
And the algorithm looks like this:
def bst_from_preorder(preorder): root = TreeNode(preorder) for value in preorder[1:]: helper(root, value) return root def helper(node, value): if value < node.val and node.left: helper(node.left, value) elif value < node.val: node.left = TreeNode(value) if value > node.val and node.right: helper(node.right, value) elif value > node.val: node.right = TreeNode(value) return node