Reconstruct tree (with markers)

You are given pre-order traversal with a slight modification. It includes null pointers when a particular node has nil left/right child. Reconstruct the binary tree with this information.

Solution

Code

def reconstruct_tree(pre_order)
    root, index = reconstruct_tree_helper(pre_order, -1)

    root
end

# Explicitly return index to simulate pass by reference
def reconstruct_tree_helper(pre_order, index)
    index += 1

    # Error input
    raise StandardError.new('Invalid input') if index >= pre_order.size

    # Handle nil left/right child
    return nil, index if pre_order[index].nil?

    # Handle non-nil children
    node = BinaryTreeNode.new(pre_order[index])
    node.left, index = reconstruct_tree(pre_order, index)
    node.right, index = reconstruct_tree(pre_order, index)

    node, index
end

Complexity

• Time: O(n) to traverse the entire pre-order list
• Space: O(h), since we are recursing along the height of the tree and storing temp index variables.