This post is part of the Algorithms Problem Solving series.
Problem description
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 preorder traversal.
(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 node.right.)
It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Examples
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Solution
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[0])
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