Data structures

Have you observed something? When ever you are writing code using any IDE, if you write mismatched brackets, immediately an error is shown by IDE. So how does IDE  know if an expression is having balanced brackets? For that, the expression must have equal number of opening and closing brackets of matching types and also they must be in correct order. Let us look at some examples (a+b)*c+d*{e+(f*g)}   - balanced (p+q*[r+u )] - unbalanced (p+q+r+s) ) - unbalanced (m+n*[p+q]+{g+h}) - balanced So we do we write a program to check if an expression is having balanced brackets? We do need to make use of stack to store the brackets. The algorithm is as follows Scan a character - ch from the expression If the character is opening bracket, push it to stack If the character is closing bracket pop a character from stack If popped opening bracket and ch are not of same type ( ( and ) or [ and ] ) stop the function and return false Repeat steps 2 and 3 till all characters are scanned. On...

How do we convert a postfix expression to infix expression? A postfix expression or a "Reverse polish notation" is useful for programming. Because our programs can easily evaluate a postfix expression. But for humans, postfix expressions are difficult to understand. So is it possible to convert a given postfix expression to infix expression? Why not? It is possible with the help of stack data structure.  Remember that when converting an expression from infix to postfix , we used operator stack. But in this case we need an operand stack. What we need to do is - we extract values from expression. If there is an operand, we push it to stack. If there is an operator encountered, we pop two most recent values from stack, apply operator to them, enclose them in paranthesis and push the expression back to stack. This procedure is continued until the entire expression is scanned. In the next step, the content of stack is popped out - which will be our infix expression. So let me bul...

Towers of Hanoi is a popular mathematical puzzle invented in 1883 by French mathematician Eduoardo Lucas. It is also a popular example in coding world because it is a typical example where a recursive solution is much easier than iterative solution. In the puzzle, there are 3 rods and n discs of different sizes. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. Gif file from wikipedia Aim of the game is to transfer these  n discs to the 3rd rod, using 2nd rod as temporary location, but keeping in mind that only one disc can be moved at a time. a larger disc can not be placed above a smaller disc. How do we solve this puzzle? If some how we move n-1 discs to 2nd rod in correct order, we only have largest disc in 1st rod. And it can be moved to 3rd rod. So now we need to find a method of moving n-1 discs from 1st rod to 2nd rod in correct order. Again we can use 3rd rod for intermediate stora...

I came across this question in the net. Given a binary search tree, convert this into a sorted doubly linked list. Do not create any nodes, but just modify the links. Just like a DLL, binary tree node also has two links. But they are named left and right. What if we assume left is previous link and right is next link? OK, we don't even have to modify the structure of the nodes. Next important part is "sorted". We need a sorted DLL. Don't you get the idea now. Which traversal visits the nodes in ascending order or gives sorted output? In order traversal! That's right. So we need to visit the nodes in in-order traversal, store previous node in a static variable, and link this previous node to the next node visited using previous (left) and next(right) links. Now how do we determine the head of DLL? It should be the tree-minimum. So we can find tree minimum and set this as head. Or we can use in order traversal and set the node which has no previous node visited as h...

This is one of the interview questions. Given a binary tree, find out whether it is a binary search tree. A binary search tree is an ordered binary tree which satisfies  binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree. A binary Search Tree   This diagram shows a BST, because each node has key value larger than left subtree and smaller than right subtree. Binary Tree but not a Binary search tree This is not a binary search tree because key value of left child of root is larger than 2. And key value of node 7 is has a right child whose value is lesser than 7. How to write a function If the in order traversal output does not give key values in ascending order, then the tree is not a binary search tree. But inorder is a recursive function. So we can not directly compare values. We need to use a global variable to store the valu...

A stack data structure is a versatile data structure which is useful whenever we want output to be reverse of input, or we want a LIFO - last in first out behavior Image from Wikipedia . A function call in most languages employs a stack. The parameters and local variables are pushed to call stack. And a return statement pops out most recent call stack. Similarly when we want to check if an expression has balanced brackets, we can use a stack to store brackets. Top of stack:  Unlike a linked list where elements can be added to the end of list or beginning of a list, values are always added to the top of the stack. Just like a plate is added to the top of a stack of plates. And a value is always removed from top of the stack - similar to a stack of plates again. A stack abstract data type should define three functions push - push function inserts a value at the top of stack  pop - pop function removes a value from top of stack isempty - isempty function checks if the stack is em...

In this post we will write some functions for a binary search tree. Find minimum of a binary search tree: This function is quite simple. In a binary search tree, every node has values smaller than itself on left sub tree and values larger than itself on right subtree. So as we move to left, values get smaller and smaller. Which means that the left extreme node is our minimum value. So if you keep traversing to left until you reach NULL, the last node is tree minimum. int tree_minimum (NODEPTR nd) { while (nd -> left != NULL ) nd = nd -> left; return nd->val; } Count the total number of nodes in a binary search tree: This one needs a recursive function. Total number of nodes in a binary tree = total number of nodes in its left subtree + 1 + total number of nodes in right subtree And there is no recursion if node is NULL and the call must return 0. And here is the function. int count_nodes (NODEPTR nd) { if (nd == NULL ) return 0 ; else return ...

Mathematical expressions can be written in 3 different methods - infix, postfix and prefix. Infix notation All these days we have been using infix notation. In this operators are written between the operands. Some operators are having higher priorities than others. If some expressions are enclosed in brackets, then they are evaluated first. e.g.     (A+B)*C Here + operator will operate on A and B as it is between them. Though * has higher priority, as A+B is enclosed in brackets, that is evaluated before multiplication. Postfix notation In a postfix notation - also called Reverse Polish Notation, operator is written after the operands. The operator operates on two operands to its immediate left. And expressions are always evaluated from left to right. Brackets do not have any effect on this. e.g. (A+B)*C in postfix is  AB+C* A+B*C+D in postfix is ABC*+D+ Prefix notation In a prefix notation, operator is written before the operands. And just like postfix, expressions ...