data structures and algorithms

Tries for Text Processing

Introduction Now that we have talked so much about efficient ways of pattern finding using Boyer Moore and KMP algorithm. Let us try and understand other aspects of Text Processing as well. This post will mostly focus on using tries for text processing, storing text efficiently and also discuss about data structures which may make more sense when we talk about storage and retrieval of text based on some given criteria. Here are some real world problems which often demand quicker answers: Ever wondered why you are able to search a word in a dictionary so fast? How do you think one w...
Read More

Pattern Finding – Boyer Moore

Introduction String matching problems are important part of many Programming Contests and also find applications in real world problems. Imagine you are asked to implement a text editor. What are few of the most common operations in a text editor? Copy and Paste. Search and Replace. The performance of your text editor will completely depend on how efficiently it can search and/or replace patterns in a huge text. Basics of Pattern Finding In a given pattern matching problem, we have two strings one is called the text T and the other is called the pattern P. The task is to find th...
Read More

Inorder Predecessor of node in Binary Tree Using Parent Pointer

Introduction This is the seventh article in the Tree Traversals - Online Classes. This article presents ways to find out inorder predecessor of node in binary tree. As we have already read about the Inorder Successor it wont take much effort to understand the predecessor. Definition - Inorder Predecessor of node in Binary Tree If a node K is called the inorder predecessor of node N then N must be visited immediately after K in a inorder traversal of the tree. Below is a more formal definition of Inorder Predecessor: If the node has a left sub-tree, then inorder predecessor is the ...
Read More

Inorder Successor of node in Binary Tree Using Parent Pointer

Introduction This is the sixth article in the Tree Traversals - Online Classes. This article presents ways to find out inorder successor of node in binary tree. Before we jump into the code it would be good to correctly define the meaning of the problem. Definition - Inorder Successor of node in Binary Tree If a node K is called the inorder successor of node N then K must be visited immediately after N in a inorder traversal of the tree. Below is a more formal definition of Inorder Successor: If the node has a right sub-tree, then inorder successor is the left most node of the rig...
Read More

Level Order Tree Traversal

Introduction This is the third article in the Tree Traversals - Online Classes. I have written many articles about non-linear data structures and their traversals. But the more you dive in you can find many more ways to traverse a tree. Here we try to solve the level order tree traversal for a binary tree and we will also try to figure out other variations of this traversal. This can we precisely extended for a n-ary tree as well. Defining the problem Let us consider the above tree, if we follow the blue line from root till end and print all the nodes, we will end up printing the lev...
Read More

Understanding Search Trees – Red Black Trees

Introduction This article is to highlight the importance of having a Search tree with minimum height and revisit couple of data structures which can guarantee a minimum height Tree. Understanding Search Trees - Red Black Trees An evolution of BST that aim to keep the tree balanced without affecting the complexity of the primitive operations. This is done by colouring each node in the tree with either red or black and preserving a set of properties that guarantees that the deepest path in the tree is not longer than twice the shortest one. A red black tree is a binary search tree with the...
Read More

Data Structures and Algorithms – Recursion

Introduction The article Data Structures and Algorithms – Recursion is the third in series, of online course for Data Structure Algorithm. This is an effort to introduce and explain the Recursion methodology of algorithm design and programming. We will try to write some recursion based code and analyze the complexity of the algorithms in detail. Recursion It is the concept of defining a method that makes a call to itself and the call is termed as a recursive call. This is a readable and still efficient way of designing algorithms in the scenario where the problem in hand can be redefined by...
Read More