# Array Implementation of Binary Tree

## Array Implementation Of Binary Tree

There are multiple ways of implementing a binary tree. In this article, we will be discussing about the array implementation of binary trees

For example, if we want to implement a binary tree given below as an array : Since, this binary tree contains 3 levels, to implement this tree as an array, we need
`1 + 2^0 + 2^1 + 2^2 + 2^3 = 16` nodes. After that, we will store the level order traversal of the tree into the array.
So the array would look like this :
`[-1, 3, 5, 6, 11, 8, 9, -1, 9, -1, -1, -1, -1, -1, -1, -1 ]`
`-1` in the above array means that the corresponding position is blank.
Note that the `0th` position in the above array is intentionally left blank.

### Parent

Using the above array implementation of binary trees, we can use the following function to find parent of any node situated at position `i`.

``````Parent(i) {
return i/2
}
``````

For example, the node with value `8`, is situated at position `5` within the array. Therefore, according to the `Parent` function above, it’s parent will be located at index `5/2 = 2`. The node at position `2` is `5`, which is indeed the parent of node `8` as you can check from the diagram above.

### Left Child

Using the array implementation of binary trees, we can use the following function to find left child of any node situated at position `i`

``````LeftChild(i) {
return 2*i
}
``````

For example, the node with value `5` is situated at position `2`. Therefore, according to the above function, it’s left child will be located at position `2*2 = 4`. The element at position `4` is `11`, which is indeed the left child of `5` as can be seen from the diagram above.

### Right Child

Using the array implementation of binary trees, we can use the following function to find the right child of any node situated at position `i`.

``````RightChild(i) {
return 2*i + 1
}
``````

For example, the node with value `5` is situated at position `2` in the array implementation of binary tree. Therefore, according to the above function, it’s right child will be located at position `2*2 + 1 = 5`. The element at position `5` is `8`, which is indeed the right child of `5` as can be seen from the diagram above.

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]
{"ft_lang_label":"__label__en","ft_lang_prob":0.88748676,"math_prob":0.97843444,"size":2098,"snap":"2022-40-2023-06","text_gpt3_token_len":546,"char_repetition_ratio":0.1642789,"word_repetition_ratio":0.23232323,"special_character_ratio":0.26787415,"punctuation_ratio":0.121681415,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9931632,"pos_list":[0,1,2],"im_url_duplicate_count":[null,6,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-27T14:21:07Z\",\"WARC-Record-ID\":\"<urn:uuid:380e5f2b-f9cb-4937-b7a9-3d082574b042>\",\"Content-Length\":\"151036\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:50692cdb-1678-4b02-9398-5203d153c3da>\",\"WARC-Concurrent-To\":\"<urn:uuid:0ae00ac2-fafc-44d5-8db0-e9992e9bf518>\",\"WARC-IP-Address\":\"45.79.125.9\",\"WARC-Target-URI\":\"https://prepfortech.in/interview-topics/trees/array-implementation-of-binary-tree/\",\"WARC-Payload-Digest\":\"sha1:4ZF3YKA56E55LPVYRY57RPE2WBVJKWHO\",\"WARC-Block-Digest\":\"sha1:XUWTKPFA33HX7R7MSES5CRF5P7EW3PS2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030335034.61_warc_CC-MAIN-20220927131111-20220927161111-00495.warc.gz\"}"}