Theory

We have covered some basics about the tree in the previous posts- The TREE data structure Binary Trees Structure of Binary Trees Now let us try to see, how we can traverse a tree. In order to process trees, we need a mechanism for traversing them and that forms the subject of this post. The process of visiting all nodes of a tree is called tree traversal. Each of the nodes is processed only once but they maybe visited more than once. As we have already seen that in linear…

We learned about trees and binary trees in the following posts:- The tree data structure The basics of Binary Tree Now let us try to define the structure of the binary tree. For simplicity, assume that the data of the nodes are integers. One way to represent a node (which contains the data) is to have two links which points to the left and right children along with data fields as shown below: Please note that in trees, the default flow is from parent to children and showing directed branches…

A tree is called a binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right sub-trees of the root. Generic Binary Tree Types of Binary Trees Strict Binary Tree: A tree is called a strict binary tree if each node has exactly two children or no children. Full Binary Tree: A binary tree is called a full binary…

A tree is a data structure similar to a linked list but instead of each node simply pointing to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non-linear data structure. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. In trees ADT (Abstract Data Type), order of the elements is not important. If we need ordering information, linear data structures like linked lists, stacks, queues etc can be…

In C, struct keyword must be used for declaring structure variables, but it is optional in C++. For example, following program gives error in C and works in C++. And following program works in both C and C++.

We have discussed some very basic data structures. Sometimes, we need to decide which data structure to use at which place. Although is there is no hard and fast rule of using a data structure in a specific scenario, the below guidelines can help for general cases. For our program to be very efficient we must be aware of the sample data, our code needs to handle and a data structure should be used accordingly. Ordered Array :- If amount of data is small and predictable and search speed is…

The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct definitions of Auxiliary Space and Space Complexity. Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input. We can also say that the way in which the amount of storage space required by an algorithm varies with the size of the problem…

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc. However, any given sorting algorithm which is not stable can be modified to be stable. There can be sorting algorithm specific ways to make it stable, but in general, any comparison based sorting…

We have been discussing the time complexities of each of the algorithm that we have discussed. Let us try to analyze, how these time complexities are calculated. O(1) Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function. For example swap() function(which interchanges two numbers) has O(1) time complexity. A loop or recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1). O(n)…

Question: What is a wild pointer in a program? Uninitialized pointers are known as wild pointers. These are called so because they point to some arbitrary memory location and may cause a program to crash or behave badly. This can be understood from the below examples. Please note that if a pointer p points to a known variable then it’s not a wild pointer. In the below program, p is a wild pointer till this points to a. If we want pointer to a value (or set of values) without…