TREES DATA STRUCTURES

6 min readSep 26, 2022

Basic overview of trees in data structures

Introduction

A tree is a non-linear and hierarchical data structure consisting of a collection of nodes such that each node of the trees stores a value and a list of reference to other nodes. Data in a tree is stored in a hierarchical structure.

Tree structure

Node is an entity that contains a value/key and pointers to its child nodes (A, B, C, D, E, F, G), the last nodes of each path are called the leaf/external nodes(D, E, F, G). Edge of a tree is the link between two nodes.

Parent node is a node which is the predecessor of a node(B,C) while a child node is the immediate successor of the node(D,E).

Root node top most node of a tree which does not have any parent(A), a non-empty tree must contain exactly one root node.

Sub-Tree is any node of a tree along with its descendants.

Important properties of a tree

Traversing a tree is done by depth first search and breadth first search.
its hierarchical model.
it has no loop or circuit.

Basic tree operation

Create a tree, insert data, search specific data in a tree, traveling a tree(pre-order, post-order, in-order).

Types of tree data structures

Binary Search Tree are used for various searching and sorting algorithms. It shows that the value of the left node is less that its parent while the value of the right node is greater than the parent.
Binary tree node has a maximum of two child nodes.
General tree has no restrictions in the number of nodes, parent nodes can have many child nodes.
Balanced tree is one which the height of the left sub-tree and the right sub-tree is equal or differs by 1 .

Application of trees

It is the shortest path tree used in the routers to direct the packets to the destination(Spanning tree)
Binary search
Storing hierarchical data.

Tree Traversal

There are three ways of traversing a binary tree.

In-Order Traversal
Pre-Order Traversal
Post-Order Traversal

In-order Traversal (Left, Root, Right)

In the In-order tree traversal, we traverse a binary tree by first visiting all the nodes in the left sub-tree and then the root node and finally the right sub-tree of the tree.(L, RT, R).

Left sub-tree ->root ->right sub-tree

Starting from the left -sub tree from the root, 1(L), 2(Rt),3(R)
Then go to the root 4(RT).
Finally Right sub-tree X(L), 5(RT),6(R). X means there is nothing on the left side of the right sub-tree

After traversing all the elements in the tree we get the in order traversal as:

1 -> 2 ->3 ->4 ->5 ->6

Representation in a stack which is a linear data structure that follows the principles of Last In first Out(LIFO). The last element inserted into the stack will be removed first. We don’t have to create the stack ourselves because recursion maintains the correct order for us.

inorder(root->left)
display(root->data)
inorder(root->right)

github link for the inorder class and node class

Preorder traversal(RT, L, R)

In the pre-order tree traversal, we first visit the root node, then the left sub tree from the root and finally right sub tree.

display(root->data)
preorder(root->left)
preorder(root->right)

Starting from the root 4(RT).
Move to the left sub tree, start again from the root 2(RT), 1(L), 3(R)
Move to the right sub tree, start from the root 5(RT), x(L),6(R). X means no element, you don’t need to insert the x, you can leave it out but I have added it to indicate there is no value in the left side of the right sub tree.

4(RT), 2(RT),1(L),3(R),5(RT),6(R)

After traversing all the elements in the tree we get the pre-order traversal as:

4-> 2-> 1 ->3 ->5 ->6

Pre- order github link

node class

Post Order Traversal(L,R,RT)

In the post-order tree traversal, we first visit all the nodes in the left sub-tree, then all the nodes in the right sub tree and finally the root node.

postorder(root->left)
postorder(root->right)
display(root->data)

Starting from the left sub tree, traverse all the nodes (L, R, RT), 1(L), 3(R), 2(RT)
Move to the right sub tree x(L), 6(R), 5(RT)
Finally the root node 4(RT)

1(L), 3(R), 2(RT),x(L), 6(R), 5(RT), 4(RT)

After traversing all the elements in the tree we get the post-order traversal as:

1->3 ->2 ->6 ->5 ->4

github code link

Node class link

Binary Search Tree(BST)

A binary search tree is a data structure that quickly allows you to maintain a sorted list of numbers. It is used to search for the presence of a number in O(log(n)) time complexity. It is a binary tree because each tree node has a maximum of two children nodes.

Properties

The left sub-tree of a node contains only nodes with keys lesser than the node’s key.
The right sub-tree of a node contains only nodes with keys greater than the node’s key.
The left and right sub-tree must also be a binary search tree.

Operation in a binary search tree

Insertion
Deletion
Search

Search Operation in BST BreakDown

Read the search element/item/number
Compare the search element with the value of the root node in the tree.
If the values are matched, display “Node is found” and terminate the function.
if both are not matched, then check whether search element is smaller or larger than that node value.
If the search is smaller, then continue with the search process in the left sub-tree.
If the search is larger, then continue with the search process in the right sub-tree.
Repeat until you find the exact same element or until the search element is compared to the leaf node.
If we reach to the node having the value equal to the search value then display “Element is found” and terminate the function.
If we reach to the leaf node and if it is also not matched with the search element, then display “Element is not found” and terminate the function.

The algorithm depends on the property of BST that if each left sub tree has value less than root and each right sub-tree has greater than the root. We can only search the left sub-tree if the value is less than the root.

Algorithm

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)