DSA part-1

DSA Part-1 (Data Structure and Algorithm)

Binary tree structure

Binary tree structure is defined as a tree  data structure with at must 2 children. Since each element in a binary tree can have only 2 children we typically name them the left and right child.

Binary Tree Representation

A Binary tree is represented by a pointer to top most node of the tree.

Binary tree node contains the following parts

• Data
• Pointer
• Left child
• Pointer to right

Basic operation of the Binary tree

• Inserting an element
• Removing an element
• Transverse an element

Auxiliary operation on Binary tree 

• Finding the height of the tree
• Find the level of the tree 
• Finding the size of the entire tree

Queue Data Structure

A Queue is linear structure used to store the data effectively and efficiency.

• It follows first in first out (FIFO) elements are inserted at end of Queue and deleted from beginning of an Queue.
• Queue stores different types of the element  such as integer , strings etc.
• Queue can be implemented using Array or Linked list.

Types of Queue

• Circular Queue
• Priority Queue
• Double ended Queue for Dequeue
• Linear Queue

Queue Operations

• Push : Add element to an stack
• pop : Remove the top element of on stack
• IsEmpty : True , if stack is empty false , if stack is not empty.

Stack Data structure 

A stack is linear data structure that follows the principle of last in first out (LIFO). This means the last element inserted inside the stack is removed first.

• Put a new plate on Top
• Remove the Top plate

Basic operation of stack

• push
• pop
• IsEmpty
• IsFull
• peek

Working of stack data structure 

• A pointer called TOP is used to keep track of the top element in the stack.
• When Initializing the stack , we set  its value to -1 so that we can check if the stack is empty by comparing Top == -1
• On pushing an element ,we increase the value of TOP and plane the new element in the position pointed by the TOP 
• On poping an element , we return the element pointed to by TOP and reduce its value.
• Before pushing we , check if the stack is already empty.

Stack Time complexity 

For the array-based implementation of a stack , the push and pop operations take constant time i.e O(1)

Application of stack Data structure 

• To reverse a word
• In compilers
• In Browsers