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...

Structures in C++ are user defined data type that can contain multiple variables  of different data types. They can also contain member functions. Functions in structures are public by default. Structure declaration example : struct Dog { int age; char name[50]; char owner[100]; string type; }; Here structure is Dog with entries age, name , owner and type. To create structure variables d1 and d2, struct Dog d1; struct Dog d2; Accessing variable values : strcpy(d1.name, "Shera"); strcpy(d2.name, "Jimmy"); d1.type = "Labrador"; Structures can be used as any other variables to pass to other functions and to create structure pointers: void myfunction(struct Dog d) {} // function with structure as argument struct Dog d1; struct Dog * dp; // structure pointer dp = &d1; Typedef can be used to avoid writing struct while creating variables, such as: typedef struct { . . . }Dog;...

Call by Value and Call by Reference are two ways of passing parameters to a function. Call by Reference    -> modifies the passed value in the main function or the calling function                                  -> actual arguments are passed to function                                  -> can be done using pointers or references Call by Value         -> does not modify value in the main function                                 -> copy of arguments is passed to function Example,  void modref( int & x ) { x = 0; } // call by reference using reference void modp (int * x ) { *x = 1; } // call by reference using pointer void nomod (int x ) { x = 30; } // call by value ...

References in C++ are very important as they can help you significantly reduce the running time of your code. A reference is simply another name to the same data value. For example, here x_ref is a integer reference to x : int x = 10; int & x_ref = x; // reference initialization cout<<x_ref; // x_ref and x are same, i.e. 10 x_ref = 20; cout<<x; // x is now 20 A reference is declared by using the & sign [the & sign is also used to get memory location of a variable].  It is necessary to initialize a reference at the time it is declared. It is because you cannot have NULL references, so you need to initialize an explicit value to which declared reference is a reference to.  When you modify a reference, the original value also changes. Another example, string s = "Hello, this is original string"; string &x = s; x = "Modified string"; cout<<x; // outputs Modified string cout<<s; // outputs Modi...

A variable is a memory location which can store a value and each memory location has its own   address. Memory addresses are represented by long hexadecimal numbers. To access the address of any variable we need to use & operator. Such as: int x = 10; cout<<x; // this will output 10 cout<<endl; // next line cout<<&x; // this will output the address of x Pointer is a storage entity that can hold the address of any variable. You need to specify the type of variable whose value pointer will hold, at the time of declaration. You can declare a pointer as : int * p1; char * p2; string * x; p1 is pointer for integer variable p2 is pointer for char variable x is pointer for string variable Similarly, you can create a pointer for any valid data type in C++. To use a pointer, you need to assign it the address of the variable that it will p oint to. You can access the value stored in the variable that p points to by using...

Strings are character arrays whose last value is '\0', null character. You can define a string as : char str[] = {'h', 'e', 'y', '\0' } or as  char str[] = "hey"; // str can be modified or as char * str = "hey"; // str cannot be modified, will cause segmentation error const char * str2 = "heyy"; // will not cause warning, still cannot modify or by using the string data type string s = "hey"; The string class, included as #include <string> provides various functions to perform string operations. Some of them are : strlen(str) -> length of str strcat(str1,str2) -> concatenate str2 at the end of str1 strcpy(str1,str2) -> copy str2 into str1 When you declare as char[int] then you cannot directly assign value using = rather you need to use strcpy

Arrays are among the most basic data structures in computer science. An array is simply, a data storing entity that stores homogenous data values. For example, if we need to store a sequence of integer values such as 3, 5, 7, 9 and 11 then rather than declaring 5 integer variables, we can use 1 integer array to store all the five values. int array[] = {3, 5, 7, 9, 11}; location 0, accessed by array[0] contains the value 3 location 1, accessed by array[1] contains the value 5 location 2, accessed by array[2] contains the value 7 location 3, accessed by array[3] contains the value 9 location 4, accessed by array[4] contains the value 11 The int before array, in array declaration describes the type of data that the array can store. It can be any valid data type such as int, string, char, float, etc. Arrays can be single dimensional or multi dimensional. The array used in the example above is single dimensional. A two-dimensional array with 2 rows and 3 columns can be de...

I n-Place Algorithms are required to solve those problems which have limited memory constraints. You are not allowed to use extra memory and hence all operations need to be performed on the original data structures themselves. Usually, the algorithms should use O(1), constant memory. You are allowed to declare variables but not complete data structures. For example, you are given an array [1,2,2,4] and you need to delete all values which are equal to 2. One approach could be by checking each element of the array. If it is 2 then skip otherwise store the value in a new array and at the end of the loop[ when traversed every element of array ], return the new array. But this approach is not In-Place as it requires O(n) memory [ Worst case when no element of given value in array ]. For an In-Place algorithm we would need to delete the elements with value in the original array and then return the original array as the answer to the problem.