"construct binary tree from array" Code Answer's

construct binary tree from array

By Santino on Mar 22, 2021

When implementing a binary tree as an array it helps to have a clear visualization of how the two representations mirror one another, and review the mathematical structure that underlines the relationship.

If we consider 0-indexed arrays the mathematical relation can be broken down as such,

The root node has index 0
For the i:th node (i is the array index) we have that (verify)

The left-child of the node has the index 2i + 1
The right-child of the node has the index 2(i + 1)
The parent of a node has the index floor((i-1)/2)
So, for the binary tree

Binary tree

if we let - denote null, is represented as such

[0:a, 1:b, 2:c, 3:d, 4:e, 5:-, 6:-, 7:-, 8:-, 9:g, 10:-, 11:-, 12:-, 13:-, 14:-]
So now to create the OO representation from the array you simply apply these indexing rules. So, since you know that the root node is a then we get its children at:

Left: 2*0 + 1 = 1 => b
Right: 2*(0 + 1) = 2 => c
Pseudo code
for (int idx = 0; 2*(idx + 1) < len(arr); idx++) {
    if (arr[idx] == null) {
        // There is no node to add for this index
        continue;
    }

    TreeNode t = null;

    if (idx == 0) {
        // Root node case
        t = TreeNode(val: arr[idx]);
        binary_tree.add(id: idx, node: t);
    }

    // We do not know if these exist yet
    int left_idx = 2*idx + 1; 
    int right_idx = 2*(idx + 1);

    if (left_idx >= len(arr)) {
        // left_idx is out of bounds with respect to the array, 
        // and by extension so would the right node be
        continue;
    }

    TreeNode left = null;
    TreeNode right = null;

    if (arr[left_idx] != null) {
        // This node has never been encountered before
        // and it is non-null so it must be created.
        //
        // Since we know we have a root node then there is
        // no need to check if the tree already contains this
        // node, it simply is not possible. Ditto for the right
        // node.
        left = TreeNode(val: arr[left_idx]);
        binary_tree.add(id: left_idx, node: left);
    }

    if (right_idx >= len(arr)) {
        // There cannot be a right child
        continue;
    }

    if (arr[right_idx] != null) {
        // This node has never been encountered before
        // and it is non-null so it must be created.
        right = TreeNode(val: arr[right_idx]);
        binary_tree.add(id: right_idx, right);
    }

    // It does not matter if left or right is null
    t.set_left(left)
    t.set_right(right)    
}

Add Comment