Adventures in Computer Science

A Binary Heap is a complete binary tree, which satisfies either the min-heap property or the max-heap property .  Min-Heap property - Root is element with minimum value. - Value at each node is greater than or equal to the value at its parent node. Max-Heap property - Root is element with maximum value. - Value at each node is less than or equal to the value at its parent node. Binary Heap is partially ordered. The ordering amongst elements at the same level doesn't matter. It must satisfy only the requirements of being a binary heap. Binary Heaps can be stored in arrays as they are complete binary trees. Some applications of binary heaps include : -Priority Queues -Order Statistics -> Kth largest element, merge K sorted arrays, ... Binary Heap can be implemented using arrays. In an array starting from index 0, to access elements corresponding to a node with index n : Current Node -> n Parent of Current Node -> (n-1)/2 Left Chi...

A Binary Search Tree is a binary tree data structure with the following properties : - All the nodes in the left subtree of a node n have keys less than the key of node n - All the nodes in the right subtree of a node n have keys greater than the key of node n - There are no duplicate keys - Both left and right subtrees must themselves be binary search trees Example of BST -> These properties make it easier for up to speed up operations such as search, insertion and deletion. We can use a recursive function to search the left subtree if the target is smaller than the key of the node, if greater search the right subtree and if equal return the position of the node we're at. Insertion is always done at leaf node. Example :  #include <iostream> using namespace std; // Implementation of Binary Tree Insertion in C++ struct tree{ int data; struct tree * left; struct tree * right; }; s...

Some of the common types of Binary Tree are listed below : Full Binary Tree  - In a full binary tree, each node has either 0 or 2 children. - Each node is either leaf or has exactly 2 children. Complete Binary Tree  - All levels are full except possibly last. - All nodes in the last level are aligned towards the left.  Perfect Binary Tree  - All nodes have 2 children except leaf. - All leaf nodes are at the same level. Balanced Binary Tree  - Very good performance, O(log n) Insertion, Deletion and Search - Every level above the lowest is full - Diff is maximum 1 between left subtree and right subtree Degenerate/Pathological Binary Tree  - Each node has one child except leaf Traversal Preorder Node is visited before its left and right subtrees Postorder Node is visited after both subtrees Inorder Visit left subtree, then visit node and finally right subtree Binar...

A tree is a hierarchical data structure which consists of a set of nodes.  A tree is a graph with no cycles.  Binary Tree is a special type of tree, in which each node can only have a maximum of 2 children. In Binary Tree each node consists of :  1. Data 2. Pointer to left node 3. Pointer to right node TREE TERMINOLOGY  :  Root - Node with no parent, only one in a tree Leaf - Any node with no children Parent  - If a node is directly above node x, then it is parent of node x Child  - If a node is directly below node x, then it is child of node x Ancestor  - If a node is in the path from root to node x, then is ancestor of node x Descendant  - If a node y is ancestor of node x, then node x is descendant of node y Siblings -Set of nodes that have the same parent node A Binary Tree can be implemented in C++ as : #include <iostream> using namespace std; // Implementation of Binary Tree ...

STACK A stack is a linear data structure that only allows operations on the last added element in the stack. A stack can be visualized as a jar that is open from the top, so you can only put stuff or take out stuff from the top. Stacks are almost always with two basic operations - push and pop. Push inserts a new element in the stack from the top and Pop takes out the element at the top of the stack.  Stacks follow LIFO order (Last In First Out). A stack can be implemented using array or linked list. Top in stack is the element at the top of the stack. In C++, we can use the Standard Template Library implementation of Stack as:  #include <iostream> #include <stack> using namespace std; int main() { stack <int> x; x.push(1); x.push(2); x.push(4); cout<<x.top()<<endl; // 4 is at top x.pop(); // pops 4 x.pop(); // pops 2 cout<<x.top()<<endl; /...

Linked Lists are data structures that are similar to arrays but are not stored in contiguous memory. Linked Lists use pointers to access the next node. Logically a linked list looks like,  Each node has two variables, first variable stores the data value and the second variable is a pointer variable that points to the next node in the linked list. Arrays have O(n) Insertion operation and O(n) deletion operation [at the first position], whereas in Linked Lists these operations are O(1). However, we cannot access a linked list element directly like in array using index. Instead we have to parse through a linked list sequentially using pointers. Also, array size is fixed whereas linked lists are expandable. Linked lists also consume extra space because of pointer.  We can create a Linked List in C++ by defining a structure for node as  : struct LLNode { int data; struct LLNode * pointer; // pointer that points to...