Learn: In this article we are going to study about the **representation of binary tree**. What are the different representations of trees in the memory? What is **linked list representation of binary tree**? What is **sequential representation of binary tree**?

Submitted by Amit Shukla, on October 06, 2017

I would like to request you to please read BINARY TREE DEFINATION AND ITS PROPERTIES to understand basics of binary trees and its different types.

Let **T** be a Binary Tree. There are two ways of representing **T** in the memory as follow

**Sequential Representation of Binary Tree.****Link Representation of Binary Tree.**

Consider a Binary Tree **T**. **T** will be maintained in memory by means of a linked list representation which uses three parallel arrays; **INFO**, **LEFT**, and **RIGHT** pointer variable **ROOT** as follows. In Binary Tree each node **N** of **T** will correspond to a location **k** such that

**LEFT [k]**contains the location of the left child of node**N**.**INFO [k]**contains the data at the node**N**.**RIGHT [k]**contains the location of right child of node**N**.

**Representation of a node:**

In this representation of binary tree root will contain the location of the root **R** of **T**. If any one of the subtree is empty, then the corresponding pointer will contain the null value if the tree **T** itself is empty, the **ROOT** will contain the null value.

**Example**

Consider the binary tree **T** in the figure. A schematic diagram of the linked list representation of **T** appears in the following figure. Observe that each node is pictured with its three fields, and that the empty subtree is pictured by using x for null entries.

**Binary Tree**

**Linked Representation of the Binary Tree**

Let us consider that we have a tree **T**. let our tree **T** is a binary tree that us complete binary tree. Then there is an efficient way of representing **T** in the memory called the sequential representation or array representation of **T**. This representation uses only a linear array TREE as follows:

- The root
**N**of**T**is stored in**TREE [1]**. - If a node occupies
**TREE [k]**then its left child is stored in**TREE [2 * k]**and its right child is stored into**TREE [2 * k + 1]**.

**For Example:**

Consider the following Tree:

**Its sequential representation is as follow: **

Are you a blogger? Join our Blogging forum.

Comments and Discussions

.resCodeAS1 { display: block; width: 320px; height: 50px; }
@media(min-width: 300px) { .resCodeAS1 { display: none; } }
@media(min-width: 480px) { .resCodeAS1 { display: none; } }
@media(min-width: 750px) { .resCodeAS1 { display: block; width: 336px; height: 280px; } }
(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

solved programs: » C » C++ » DS » Java » C# |

aptitude que. & ans.: » C » C++ » Java » DBMS |

interview que. & ans.: » C » Embedded C » Java » SEO » HR |

Like other websites, this site uses cookies to deliver relevant ads based on your interest, by using our website, you acknowledge that you have read our privacy policy.

Close