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
# data structures and algorithms

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