Self doubt

Question

I have a confusion regarding the array implementation of binary tree ,i.e what are the index locations of the left child of a node whether it is 2i+1 or 2i and same for right child ,can anyone explain?

Comments

Array indexing , implicitly in C , starts from 0 . So , for left child it is 2i+1 and 2i+2 for right child.
In case indexing starts from 1 , i.e &A[1] is the base address of your array , then left child is 2i and 2i+1 is right child.

---

Thanks ,one more thing ,is this indexing same for complete binary tree and heap as well?

---

Complete binary tree and binary heaps are special cases of binary tree itself.

---

@prashant, let if a internal node doesn't have left child, then still is it correct ?

---

If an internal node doesn't have a left child , then we can keep some marker at array index 2i+1 which can tell that there is no left child present for the parent internal node . Array representation is not usually used for storing binary trees (unless it is a heap) , since too much space is wasted if the tree is sparse and right skewed . Linked List representation is used in that case . @Shaik Masthan kindly rectify wherever i went wrong.

---

Ok got it

---

no need of heap, if it is complete binary tree, we can happily use array representation.

---

:)

Answer 1

Left child = 2i ,

right child = 2i+1

If array is start from index 1.