Background Info: I'm reading a book on C programming and this section is related to Binary Trees, BST's, as well as utilizing arrays to hold the nodes of a BST.
The author says the following: "To illustrate, suppose an array of 100 elements is used to hold a tree. If the values 1, 2, 3, 4, 5, 6, and 7 are inserted in that order, they will be stored in locations 1, 2, 4, 8, 16, 32, and 64, respectively."
The author also derives a formula for how the nodes should be placed in the array as shown below.
Formula if indexing starting from 0: " The parent of node N is node N/2. The left child of node N is node 2N. The right child of node N is node 2N + 1. "
Formula if indexing starting from 1: "The parent of node N is node (N + 1)/2 - 1. The left child of node N is node 2N + 1. The right child of node N is node 2N + 2"
In the BST for the values 1 to 7, 1 is a child of 2, and 2 is a child of 4 for the left subtree.
Question: How is what the author stated possible, in other words, how can we have a BST where the array locations are 1, 2, 4... for values 1, 2, 3 ... when the author tells us that the parent node is found by N/2. So for N = 1, where the value is 1, the actual BST would show that the parent is 2 which based on what the author says should be in location 2. But when I utilize the formula, the parent is at location 0?
Any help would be appreciated, thank you.