multixlab

Array representation of a binary tree

Data-structures  #binary-tree  #data-structures 

If a binary tree is represented by array then for any node present at index i, it’s left child will be at (i * 2) + 1, right will be at (i * 2) + 2 and prent will be at ⌊(i - 1) / 2⌋.

    node = i
    left-node = (i * 2) + 1
    right-node = (i * 2) + 2
    parent-node = ⌊(i - 1) / 2⌋ // floor value

Example 1.

When a complete binary tree is represented by an array (as in this example) then it will always have consecutive non-null values on the left side of the array but it can have nulls at the end of array

Example 2.

Note that even the left nodes of 2 and 7 are not in the tree but still there should be an index reserved for these nodes. For example, if 3 (right child of 2) is stored at index 4 then it will become left child of node 7 which is wrong.

Related posts

top