Tree data structure

Tree Data structure

Till now we have seen linear data structures such as arrays and linked lists. In these data structures, we had only one child following the previous parent.

5 is parent of 7
7 is parent of 3
3 is parent of 4

Tree are hierarchical data structures. Here each node can have multiple children.

A popular implementation of Tree is a Binary tree where each node has at most 2 children (known as the left child and right child). The top most node is known as the root of the tree similar to the head node in a linked list. The node directly above some node is called its parent.

Application:

Trees can are used in various applications that we see every day. 

For example, the directory structure that we see in our operating systems (file explorer in Windows, finder in MacOS) is a great example of using tree where each folder is a node and each sub folder are its children, the files can be considered as leaf nodes i.e. the bottom most nodes in the tree which have no children.

Another great example is the databases which are implemented by using B-trees or B+ trees.

Trees are also used for maintaining data in a sorted fashion and improve searching speed using Binary Search Trees (BST) and Balanced BST.

We are going to see all these various kinds of trees and algorithms that will help us make these trees and traverse or manipulate them.

Code in Python:

A typical implementation of a tree can be as follows:

1. Tree Node:

# A Python class that represents an individual node 
# in a Binary Tree
class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key

2. Binary Tree:
# A class that represents an individual node in a
# Binary Tree
class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key
 
 
# create root
root = Node(1)
''' following is the tree after above statement
        1
      /   \
     None  None'''
 
root.left      = Node(2);
root.right     = Node(3);
   
''' 2 and 3 become left and right children of 1
           1
         /   \
        2      3
     /    \    /  \
   None None None None'''
 
 
root.left.left  = Node(4);
'''4 becomes left child of 2
           1
       /       \
      2          3
    /   \       /  \
   4    None  None  None
  /  \
None None'''

credits: GeeksForGeeks

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal