Tree Data Structure

5 min readMar 30, 2025

Dive into the key concepts of tree data structure.

The tree is a non-linear hierarchical data structure, it is the hierarchical relationship of Nodes with each other as a parent-child. It is a collection of nodes, vertices, and edges. real-world example is the folder structure in an operating system, HTML Tags. The topmost Node is known as the root Node, and the Nodes below it are called child Nodes, which further contain their children, and so on.

If there are “n” Nodes, there will be “n-1” edges.

Important Terminologies

Root: It is the first/Topmost Node in the tree.
Parent: A Node is a parent to its very first descendants.
Child: The next Node of a parent is its child.
Siblings: Children of the same parent.
Descendants: For any Node which are its children and their children and so on.
Ancestors: For any Node, all the nodes along the path from that node to the root node.
Degree of a Node: It is the number of direct children it has.
Internal Nodes: Nodes with a degree greater than zero.
External Nodes: Nodes with a degree of zero are external/leaf Nodes.
Level: It starts from 1, which means we are at the root Node. When we move from the root Node to its next Node, then we are at level 2, and so on.
Height: It starts from 0 onwards; it counts the number of edges. At the root Node, the height will be zero, and when we move to the next Node then we are at height 1, and so on.
Depth: The number of edges from a specific Node to the root Node.
Forest: A collection of trees makes a forest.

Binary Tree

The tree of degree two, every Node can have a maximum of degree 2, which means two children, but it can have less than two children.

children = {0,1,2}

Strict Binary Tree

A strict binary tree is defined as a Node that can have either zero or two children.

children = {0,2}

Full Binary Tree

A binary tree of height “h” has a maximum number of Nodes.

Complete Binary Tree

The type of tree in which all levels are completely filled from left to right, except possibly the lowest one.

If a binary tree is represented in an array, there should be no blank space between the elements.

Get Owais Ahmad’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

It is suitable for an array.
A full binary tree is always a complete binary tree.

Representation of Binary Tree

Binary Tree can be represented by using either an array or links.

Array Representation

For storing a binary Tree, we have to store two things. First, all elements, second relationship between those elements, like A is a parent of B & C etc.

Store elements level by level.

Now, check for relationship preservation using the table below.

element = I

left-child = 2 * I

right-child = 2 * I + 1

parent = floor(i/2)

Linked Representation

When representing using a linked list, each Node in a binary tree contains a class or structure that contains three fields.

Data: contains the actual value or data of the Node.
Left: A pointer to the left child Node. If the node doesn’t have a left child, then this pointer is set to NULL.
Right: A pointer to the right child Node. If the node doesn’t have a right child, then this pointer is set to NULL.

Steps to create

Start by creating the root Node and then creating the left and right child. First, check for it; if it exists, then iteratively add the left and right child of the Node using the pointer to its parent using the links.

Generate it level by level.

We need a Queue Data Structure

Create root Node.
root points on that Node.
Insert the value and make its left and right pointers NULL.
Insert the address of root in Queue

Now repeat the above steps

Take out the address from the Queue
Make some temporary variable pointer “P” and point on that address
While pointing to that Node, verify whether this node has a left child. If there is, then create a new Node with the help of temporary point “t” and insert the value. Set the pointers left and right as NULL.
As this is the left child now, make “p” the left point on this new Node.
Insert the address of the new Node in Queue.
Now repeat the same steps for the right child as well, if it exits.