1 votes 1 votes 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? DS data-structures + – Winner asked Mar 17, 2019 Winner 798 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply prashant jha 1 commented Mar 17, 2019 reply Follow Share 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. 3 votes 3 votes Winner commented Mar 17, 2019 reply Follow Share Thanks ,one more thing ,is this indexing same for complete binary tree and heap as well? 0 votes 0 votes prashant jha 1 commented Mar 17, 2019 reply Follow Share Complete binary tree and binary heaps are special cases of binary tree itself. 1 votes 1 votes Shaik Masthan commented Mar 17, 2019 reply Follow Share @prashant, let if a internal node doesn't have left child, then still is it correct ? 0 votes 0 votes prashant jha 1 commented Mar 17, 2019 reply Follow Share 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. 3 votes 3 votes Winner commented Mar 17, 2019 reply Follow Share Ok got it 0 votes 0 votes Shaik Masthan commented Mar 17, 2019 reply Follow Share no need of heap, if it is complete binary tree, we can happily use array representation. 1 votes 1 votes prashant jha 1 commented Mar 18, 2019 reply Follow Share :) 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Left child = 2i , right child = 2i+1 If array is start from index 1. abhishekmehta4u answered Mar 17, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.