Construct Binary Search Tree from Preorder Traversal
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
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!