The Gateway to Computer Science Excellence
+1 vote
61 views
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
+2
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.
0
Thanks ,one more thing ,is this indexing same for complete binary tree and heap as well?
+1
Complete binary tree and binary heaps are special cases of binary tree itself.
0
@prashant, let if a internal node doesn't have left child, then still is it correct ?
+2

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.

0
Ok got it
+1
no need of heap, if it is complete binary tree, we can happily use array representation.
0
:)

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
198,591 comments
105,442 users