The Gateway to Computer Science Excellence
+1 vote
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?
in DS by (445 points) | 61 views
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.

1 Answer

+2 votes

Left child = 2i ,

right child = 2i+1

If array is start from index 1.

by Boss (36.7k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,391 answers
105,442 users