Representation of Trees

 

Different Methods to Represent a Tree

There are three major ways to represent a tree in programming:

Method	Description	Best Used For
1. Parent Array Representation	Store parent of each node in an array.	Simple, static trees.
2. Linked Representation (Nodes and Pointers)	Each node has pointers to its children.	Dynamic trees, flexible structure.
3. Adjacency List Representation	Represent tree as a graph. Each node points to a list of children.	Trees with many children per node.

1. Parent Array Representation

• Idea:
  Maintain an array parent[i] where each index i represents a node, and parent[i] gives the index of its parent node.

• Root has a parent marked -1.

Example

Node	A	B	C	D	E	F
Index	0	1	2	3	4	5
Parent Array	-1	0	0	1	1	2

• A is the root (parent = -1)

• B and C are children of A

• D and E are children of B

• F is child of C

✅ Advantage: Simple and memory efficient.
❌ Disadvantage: Finding children is slow (must scan the array).

2. Linked Representation (Nodes and Pointers)

• Idea:
  Each node is a structure that stores:

  • Data

  • Pointer to child nodes

There are two variants:

• General Tree (multiple children)

• Binary Tree (maximum two children: left and right)

---

(a) General Tree Representation

Each node stores an array or list of pointers to its children.

//Node declaration 

struct Node

{ 

int data; // A dynamic array of children 

struct Node **children; 

}

✅ Advantage: Very flexible.
❌ Disadvantage: Slightly more memory use (pointers).

(b) Binary Tree Representation

Each node stores exactly two pointers:

• left (left child)

• right (right child)

struct Node 

{ int data; 

struct Node* left; 

struct Node* right; 

};

✅ Advantage: Very useful for binary trees, heaps, binary search trees (BSTs).

3. Adjacency List Representation

• Idea:
  Model the tree like a graph: for each node, maintain a linked list of its children.

✅ Advantage: Useful for trees with many children or dynamic trees.
❌ Disadvantage: Slightly complex compared to others.