# A SHED UNDER THE TREE DATA STRUCTURE

Once again, I write on another data structure. My other data structure articles have been on linear data structures (Sequentially arranged data structures) from Linked Lists to Stacks and Queues.

Trees are **nonlinear data** **structures**(nodes can be connected to more than one node). There are different classifications of trees and more often than not, these classifications are based on the number of nodes each node in the tree is linked to. An example is a **binary tree** where each node is specified to link to two other nodes.

Trees are popularly used to show a relationship between elements which could be hierarchical or otherwise and are efficient when it comes to insertion and deletion of nodes.

**TREE DATA STRUCTURE TERMINOLOGIES**

**Root —**The first node of the tree**Path —**Sequence of linked nodes**Parent —**The preceding node**Child**— A sub-node**Internal Node**— A Node linked to parent and child nodes**Leaf Node**— A Node without a sub-node**Generations**— All Nodes in the same level**Siblings**— Nodes with the same parent**Height**— Number of levels from a root node to a leaf node

## HOW TREES ARE STRUCTURED

Every node of the tree directly or indirectly is linked to the **root node(**the first node)** **via a **path**(sequence of linked nodes), has a **parent** **node** (a preceding node) and a **child node** (a sub-node) which could be a value or null(in the case of emptiness). A node with a parent and a child is called an **internal node**, and one without a child is referred to as a **leaf node**. **Generations** spring up **sibling nodes**(nodes bound by the same parent node) as every node links to different nodes and the number of generations in the tree is the **height **of the tree

*The following should be noted about trees…*

1. No two nodes in a tree can reference the same node.

2. The root node(the first/head node) is the only node that doesn’t get referenced in the data structure.

**THE IMPLEMENTATION OF THE TREE DATA STRUCTURE (BINARY SEARCH TREE)**

The binary search tree is easy to implement, the structure is as seen below.

**PYTHON3**

class Tree:

def __init__(self, data):

self.data = data

self.left_node = None

self.right_node = Nonedef printer(self): #prints the tree

if self.left_node:

self.left_node.printer()

print(self.data)

if self.right_node:

self.right_node.printer()

It all begins with the

class and then the constructor. The instance attributes **Tree****left_node**** ****right_node**** **are** **links(addresses) to sibling nodes and the

attribute is a placeholder for elements.**data**

## OPERATIONS ON THE BINARY SEARCH TREE DATA STRUCTURE

A handful of operations one could carry out with the tree data structure, but for this article, I will be going over the ** insert **and

**operations**

*search*To understand the algorithms used on binary search trees, one must understand the concept of a binary search tree.

A binary search tree isn’t just a binary tree but also an ordered search tree. In a binary search tree, there is a pattern with which the elements are stored to aid fast searching operations.

In the binary search tree above, it is noticeable that in the subtree of every node, the value left child is less than the value of the parent and the value of the right child is greater than the value of the parent node

## INSERTING ELEMENTS TO THE DATA STRUCTURE

Inserting elements into our tree data structure, we have to create a method for that. The method checks if there’s a head(root) node, if there isn’t, a new node is created and set as root and then a new element is placed. If there is a root node then, a new(child node) is created and linked to a parent node as a left or right subtree, depending on the pattern of the binary tree.

In the binary search tree above, We notice how the right subtree contains a value greater than the parent and in the same vein, the left subtrees contain values less than that of their parent.

If we are to insert an unknown element

we could write this.**data**

**PYTHON 3**

**class Tree:**

def __init__(self, data):

self.data = data

self.left_node = None

self.right_node = None

def insert(self, data):

if self.data:

if data < self.data:

if self.left_node is None:

self.left_node = Tree(data)

else:

self.left_node.insert(data)

elif data >= self.data:

if self.right_node is None:

self.right_node = Tree(data)

else:

self.right_node.insert(data)

else:

self.data = data

**if self.data**** **checks if a head node exists and if it does, then we proceed to check the inequality of

.**data**

The

block checks that the magnitude of **if data < self.data**

to be inserted is less than that of the parent node and inserts the to the left if so.**data**

The **elif data >= self.data**** **block** **runs if **data**** **to be inserted is greater than or equal to the value of the parent node and adds

to the right node of the tree.**data**

## SEARCHING FOR AN ELEMENT IN THE BINARY SEARCH TREE

The method below searches for an element in the Binary Search Tree using the pattern of the tree.

**PYTHON 3**

**def find(self, data):**

if self.data:

if data < self.data:

if self.left_node is None:

return "Data Doesn't Exist"

return self.left_node.find(data)

elif data > self.data:

if self.right_node is None:

return "Data Doesn't Exist"

return self.right_node.find(data)

else:

return "Found it"

else:

return "Empty Tree"

**if.self.data**** **verifies that the tree contains at least, a root.

compares the value **if data < self.data**

to every left subtree, returns “ **data***Data Doesn't Exist” *in case of left subtree exhaustion.

**elif data > self.data**** **compares the value

to every right subtree, returns “ **data***Data Doesn't Exist” *in case of right subtree exhaustion.

The first

block runs when the comparison of **else**

and a value in the tree evaluates True.**data**

The last

block returns “**else***Empty Tree*” in a case where there is no root.

There it is. That’s how to insert and search a Tree data structure in the Python programming language.

You can learn about the Asymptotic Analysis which sheds light on the importance of code optimization in this article