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

$ 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 units

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

function buildTree(preorder, inorder):
    if preorder is empty:
        return null
    rootVal = preorder[0]
    root = TreeNode(rootVal)
    mid = indexOf(inorder, rootVal)
    root.left = buildTree(preorder[1..mid], inorder[0..mid-1])
    root.right = buildTree(preorder[mid+1..end], inorder[mid+1..end])
    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)$ .

HannahHi! I'm Hannah. Let me know if you need help understanding anything!