#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/binary-trees/construction-algorithm

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/binary-trees/construction-algorithm

Repovive

Construction Algorithm - Binary Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Construction Algorithm

Divide and conquer

The algorithm:

$1.$ Root = first element of preorder

$2.$ Find root's index in inorder

$3.$ Split inorder into left and right parts

$4.$ Split preorder based on this (by counting elements)

$5.$ Recurse

def buildTree(preorder, inorder):
 if not preorder:
 return null
 rootVal = preorder[0]
 root = TreeNode(rootVal)
 mid = inorder.index(rootVal)
 root.left = buildTree(preorder[1:mid+1], inorder[:mid])
 root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
 return root

Optimization: use a hash map for $O(1)$ index lookup in inorder. Pass indices instead of slicing arrays.

Time: $O(n)$ with hash map. Space: $O(n)$ .