Theory

Symbol Tables can be implemented in many ways and here are some of them. Unordered Array Implementation With this method, just maintaining an array is enough. It needs O(n) time for searching, insertion and deletion in the worst case. Ordered [Sorted] Array Implementation In this we maintain a sorted array of keys and values. Store in sorted order by key keys[i] = ith largest key values[i] = value associated with ith largest key Since the elements are sorted and stored in arrays, we can use simple binary search for finding …

Since childhood, we have all used a dictionary, and many of us have used a word processor (say Microsoft WORD) which comes with a spell checker. The spell checker is also a dictionary but limited. There are many real time examples for dictionaries and few of them are:- Spelling checker The data dictionary found in database management applications Symbol tables generated by loaders, assemblers, and compilers Routing tables in networking companies (DNS Lookup) In computer science, we generally use the term symbol table rather than dictionary, when referring to the …

Question: How many binary trees are possible with n nodes? Input: Nodes = 3 Output: Answer = 5 For, example consider a tree with 3 nodes (n = 3), it will have a maximum combination of 5 different trees In general, if there are n nodes, there exist (2n)!/(n+1)! different trees.

We discussed the basic tree traversals in this post – Basic tree traversals We learned about the pre-order traversal, in-order traversal and post-order traversal. These are standard traversals that are related with root, left sub-tree and the right sub-tree. Level order traversal follows an entirely different approach and is not related with the left sub-tree and the right sub-tree. It does not hold the same property for all the nodes and hence recursive technique cannot be applied to level order traversal. Let us try to understand with the help of …

We discussed about the basic tree traversals in this post – Binary Tree Traversals Lets take our own sample tree for understanding post-order traversal. In Post-Order traversal, the root is visited after both sub-trees are completed. Post-order traversal is defined as follows:- Traverse the left sub-tree in post-order. (Step 1) Traverse the right sub-tree in post-order. (Step 2) Visit the root The post-order traversal can then be defined in this way – The nodes of the tree will therefore be in order – 4, 5, 2, 6, 7, 3, 1 …

We discussed about the tree traversal techniques in this post- Binary Tree Traversals Please see pre-order traversal to understand the basics of visiting nodes. We have our same sample tree Now let us try to understand the In-order traversal. In in-order traversal, the root is traversed between the sub trees. In-order traversal is defined as follows. Traverse the left sub-tree Visit the node Traverse the right sub-tree So when we apply the in-order traversal on our example tree this will be done as:- We get the final in-order traversal as:- …

We learned about the different type of traversals in this post Binary Tree Traversals In pre-order traversal, each node is processed before (pre) either of its sub-trees. This is the simplest traversal to understand. However, even though each node is processed before the sub-trees, it still requires that some information must be maintained while moving down the tree. Let us consider an example In the example tree shown above, the node “1” is processed first, then the left sub-tree, followed by the right sub-tree. Therefore, processing must return to the …

We know that the ‘%’ (modulus) operator returns the remainder when a number a is divided by b. Example: 12 % 10 = 2 So, considering this in mind does the % operator work with floating point values as well? Can % be used with floating point numbers in C? The above program fails in compilation and compiler report the following error in line 5: What about Java? This behavior is different in Java. % operator can be used on floating point numbers in JAVA language. Consider following example of …

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 …