generate binary tree from array code example
Example: construct binary tree from array
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)
}