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

Comments

Post a Comment

Popular posts from this blog

Reverse alternate k nodes in a linked list

Image
Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes. Reversed alternate K nodes in a linked list Algorithm: We discussed Reversing a linked list in groups of K nodes in the previous post. The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them. """ Perform the skip after reversing the previous k nodes """ count = 0 # traverse the k nodes to be skipped while current is not None and count < k-1: current = current.next count += 1 Code in Python: # Python program to alternately reverse a linked list in group of given size k # Node class class Node: # Constructor to initialise data and next def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: # Constructor to initialise head def __init__(self): self
Keep reading

Sorted Array: Binary Search

Image
Binary Search: Binary search is useful when the input array elements are sorted. The algorithm divides the search space into half each time the element to be searched (x) is not found. It uses 3 conditions: 1. If the current element of the array is equal to x, then return the index. 2. Else if the current element of the array is less than x, then x will be present towards the right of the current element (because the array is sorted). 3. Else if the current element of the array is greater than x, then x will be present towards the left of the current element. GeeksForGeeks: Binary Search Example Code in Python 3: # Function for binary search # inputs: sorted array 'arr', key to be searched 'x' # returns: index of the occurrence of x found in arr def binary_search(arr, x): l = 0 r = len(arr) # while the left index marker < right index marker while l < r: # find the index of the middle element mid = int(l + ((r - l
Keep reading