Four Ways to Split Sentences (Without Machine Learning)

Imagine you hand someone a giant wall of text — no paragraph breaks, no structure — and ask them to read it aloud naturally. They'd instinctively pause at every period, question mark, or exclamation point[cite: 1]. That pause, that boundary between thoughts, is what sentence splitting (also called sentence boundary detection or sentence segmentation) is all about[cite: 1].

Sentence Splitting in the NLP Pipeline

1. Sentence Splitting

→

2. Tokenization

→

3. POS Tagging

→

4. Parsing / Translation

Sentence segmentation acts as the foundational preprocessing stage for downstream NLP tasks.

In NLP pipelines, sentence splitting is often the very first step before anything else — tokenization, parsing, translation, summarization[cite: 1]. If you get it wrong, everything downstream suffers[cite: 1].

The good news? You don't always need a neural network to do it well[cite: 1]. In this post, we'll explore four classical, rule-based approaches to sentence splitting — from the simplest one-liner to surprisingly robust heuristic systems — all without a single line of machine learning[cite: 1].

---

Why Is Sentence Splitting Hard?

Before diving in, let's appreciate why this isn't trivial[cite: 1]. Consider these tricky cases[cite: 1]:

• "Dr. Smith went to Washington D.C. last Monday." 3 Periods • 1 Sentence — Multiple periods within honorifics and city names[cite: 1].
• "She asked, \"Are you coming?\" He nodded." 2 Sentences — Nested punctuation inside direct quotation marks[cite: 1].
• "The price is $1.99. Buy now!" 1 Decimal • 2 Sentences — Decimal point within currency[cite: 1].
• "I work at A.I. Corp. We build robots." 2 Sentences — Abbreviation ending directly at sentence boundary[cite: 1].
• "...and that's it." Ellipsis — Multi-period sequences[cite: 1].

A naïve "split on period" approach would butcher all of these[cite: 1]. Each method we explore will get progressively better at handling such edge cases[cite: 1].

---

Method 1: Naïve Punctuation Split

The Idea

The simplest possible approach: split the text every time you see ., ?, or ![cite: 1].

Think of it like cutting a ribbon every time you see a knot[cite: 1]. Fast, simple — but sometimes you cut in the wrong place[cite: 1].

Naïve splitting truncates honorifics like "Dr." as isolated sentences[cite: 1].

Java Implementation

import java.util.Arrays;
import java.util.List;

public class NaiveSentenceSplitter {

    public static List<String> split(String text) {
        // Split on . ? or ! followed by one or more spaces
        String[] parts = text.split("(?<=[.?!])\\s+");
        return Arrays.asList(parts);
    }

    public static void main(String[] args) {
        String text = "Hello world. How are you? I am fine! Thanks.";
        List<String> sentences = split(text);
        for (String s : sentences) {
            System.out.println("|" + s + "|");
        }
    }
}

Output:

|Hello world.|
|How are you?|
|I am fine!|
|Thanks.|

Looks perfect for clean text[cite: 1]. But watch what happens with abbreviations[cite: 1]:

String tricky = "Dr. Smith lives on Oak St. He owns a cat.";
// Output:
// |Dr.|
// |Smith lives on Oak St.|
// |He owns a cat.|

Oops[cite: 1]. Dr. got split off as its own sentence[cite: 1].

When to Use It

• Clean, well-formatted text (e.g., generated text, templates)[cite: 1]
• Quick prototyping when accuracy isn't critical[cite: 1]
• Pre-processing step before a smarter method[cite: 1]

---

Method 2: Abbreviation-Aware Splitting

The Idea

The naïve method fails because it doesn't know that certain words followed by a period are abbreviations, not sentence endings[cite: 1]. The fix: maintain a blocklist of known abbreviations and skip splitting when the period belongs to one[cite: 1].

This is like a train conductor who knows certain stops are "request stops" — the train doesn't halt there unless specifically needed[cite: 1].

Abbreviation lookup workflow preventing invalid sentence splits[cite: 1].

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>
#include <algorithm>
#include <cctype>

// Lowercase a string
std::string toLower(const std::string& s) {
    std::string result = s;
    std::transform(result.begin(), result.end(), result.begin(), ::tolower);
    return result;
}

// Known abbreviations (lowercase, without the period)
std::unordered_set<std::string> ABBREVIATIONS = {
    "dr", "mr", "mrs", "ms", "prof", "sr", "jr",
    "st", "ave", "blvd", "dept", "approx", "vs",
    "etc", "e.g", "i.e", "fig", "jan", "feb",
    "mar", "apr", "jun", "jul", "aug", "sep",
    "oct", "nov", "dec", "no", "vol", "pp"
};

std::vector<std::string> splitSentences(const std::string& text) {
    std::vector<std::string> sentences;
    std::string current;
    int n = text.size();

    for (int i = 0; i < n; i++) {
        current += text[i];

        // Check if we're at a sentence-ending punctuation
        if (text[i] == '.' || text[i] == '?' || text[i] == '!') {

            // Look ahead: is the next character a space followed by uppercase?
            if (i + 2 < n && text[i + 1] == ' ' &&
                std::isupper((unsigned char)text[i + 2])) {

                // Extract the word just before the period
                std::string word;
                int j = current.size() - 2; // -2 to skip the period we just added
                while (j >= 0 && current[j] != ' ') {
                    word = current[j] + word;
                    j--;
                }

                // Check if it's a known abbreviation
                if (ABBREVIATIONS.count(toLower(word)) == 0) {
                    // Not an abbreviation — it's a sentence boundary!
                    sentences.push_back(current);
                    current = "";
                    i++; // Skip the space
                }
            }
        }
    }

    // Don't forget the last sentence
    if (!current.empty()) {
        sentences.push_back(current);
    }

    return sentences;
}

int main() {
    std::string text = "Dr. Smith lives on Oak St. He owns a cat. "
                       "Prof. Lee moved to Washington D.C. last year.";

    auto sentences = splitSentences(text);
    for (const auto& s : sentences) {
        std::cout << "[" << s << "]" << std::endl;
    }
    return 0;
}

Output:

[Dr. Smith lives on Oak St. He owns a cat.]
[Prof. Lee moved to Washington D.C. last year.]

Much better! The abbreviation list acts as a safety net for the most common offenders[cite: 1].

Limitations

• Your abbreviation list will never be complete[cite: 1].
• Single capital letters (A., B.) can still trip it up[cite: 1].
• Doesn't handle quotes, parentheses, or numbering well[cite: 1].

When to Use It

• Domain-specific text where you know common abbreviations (medical, legal, scientific)[cite: 1]
• When you can afford to curate and maintain an abbreviation list[cite: 1]

---

Method 3: Regex-Based Heuristic Splitter

The Idea

Instead of a simple split, we use regular expressions to encode multiple heuristic rules simultaneously[cite: 1]:

1. A sentence ends with ., ?, or ![cite: 1]
2. Followed by whitespace[cite: 1]
3. Followed by an uppercase letter or a quote/parenthesis opening a new sentence[cite: 1]
4. BUT NOT when the word before the period is a known abbreviation or a single letter (initials)[cite: 1]

Think of it like a traffic light system: instead of just checking one condition ("is it a period?"), we check multiple signals before deciding to stop[cite: 1].

Java Implementation

import java.util.*;
import java.util.regex.*;

public class RegexSentenceSplitter {

    // These patterns will NOT trigger a split
    private static final Set<String> ABBREVIATIONS = new HashSet<>(Arrays.asList(
        "dr", "mr", "mrs", "ms", "prof", "sr", "jr", "st", "ave",
        "blvd", "dept", "approx", "vs", "etc", "fig", "no", "vol"
    ));

    /**
     * Returns true if the word before the period looks like an abbreviation
     * or a single initial (e.g., "A.", "B.")
     */
    private static boolean isAbbreviation(String word) {
        String lower = word.toLowerCase();
        if (ABBREVIATIONS.contains(lower)) return true;
        if (word.length() == 1 && Character.isLetter(word.charAt(0))) return true; // Initials
        if (word.matches("[A-Z]([a-z]*[A-Z])+")) return true; // Acronym like "U.S.A"
        return false;
    }

    public static List<String> split(String text) {
        List<String> sentences = new ArrayList<>();

        // Regex: sentence boundary = punctuation + space(s) + uppercase or quote/paren
        // We use a lookahead so we don't consume the start of the next sentence
        Pattern boundary = Pattern.compile(
            "(?<=[.?!]['\"]?)" +   // after . ? ! optionally followed by closing quote
            "\\s+" +                // whitespace
            "(?=[A-Z\"\\(])"        // before uppercase letter, quote, or open paren
        );

        // Split on candidate boundaries
        String[] candidates = boundary.split(text);

        StringBuilder current = new StringBuilder();
        for (int i = 0; i < candidates.length; i++) {
            String part = candidates[i];

            // Get the last word of this part (before the terminal punctuation)
            String trimmed = part.trim();
            String lastWord = "";
            int lastSpace = trimmed.lastIndexOf(' ', trimmed.length() - 2);
            if (lastSpace >= 0) {
                // Remove the punctuation to get the actual word
                lastWord = trimmed.substring(lastSpace + 1);
                if (lastWord.endsWith(".") || lastWord.endsWith("?") || lastWord.endsWith("!")) {
                    lastWord = lastWord.substring(0, lastWord.length() - 1);
                }
            }

            current.append(part);

            if (isAbbreviation(lastWord)) {
                // Don't split — it's an abbreviation; keep building
                current.append(" ");
            } else {
                // Real sentence boundary
                sentences.add(current.toString().trim());
                current = new StringBuilder();
            }
        }

        if (current.length() > 0) {
            sentences.add(current.toString().trim());
        }

        return sentences;
    }

    public static void main(String[] args) {
        String text = "Dr. Smith visited Washington D.C. last Monday. "
                    + "\"Was it fun?\" asked Ms. Jones. He said yes! "
                    + "The price was $1.99. She paid immediately.";

        List<String> sentences = split(text);
        for (int i = 0; i < sentences.size(); i++) {
            System.out.printf("[%d] %s%n", i + 1, sentences.get(i));
        }
    }
}

Output:

[1] Dr. Smith visited Washington D.C. last Monday.
[2] "Was it fun?" asked Ms. Jones.
[3] He said yes!
[4] The price was $1.99.
[5] She paid immediately.

Breaking Down the Regex

(?<=[.?!]['"]?)   — lookbehind: we just passed a . ? or ! (optionally + closing quote)
\s+               — whitespace: one or more space characters
(?=[A-Z"\(])      — lookahead: next char is uppercase, a quote, or open parenthesis
  

Using lookahead and lookbehind (zero-width assertions) means we split at the whitespace without consuming the surrounding characters — perfect for keeping sentence punctuation attached to the right sentence[cite: 1].

When to Use It

• General-purpose text without extreme edge cases[cite: 1]
• When you want a balance of simplicity and accuracy[cite: 1]
• As a fast pre-processing step in an NLP pipeline[cite: 1]

---

Method 4: Finite State Machine (FSM) Splitter

The Idea

This is the most robust rule-based approach[cite: 1]. We model the sentence-splitting process as a Finite State Machine — a system that moves through a set of states as it reads characters one by one[cite: 1].

Think of it like reading a book with a bookmark and a set of sticky notes[cite: 1]. Each sticky note represents a "state" you're currently in (e.g., inside a quote, just saw a period, inside a number)[cite: 1]. As you read each character, you check your current state and decide whether to move to a new state[cite: 1].

Interactive State Machine Transition Diagram

This visual models how character input triggers state shifts in real time:

States in Our FSM

NORMAL          — reading regular sentence content
AFTER_PERIOD    — just saw a period (potential sentence end)
IN_QUOTE        — inside a double-quoted string
IN_NUMBER       — inside a decimal number (e.g., 3.14)
BOUNDARY        — confirmed sentence boundary (emit the sentence)

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SENTENCE_LEN 4096
#define MAX_SENTENCES    1024

typedef enum {
    STATE_NORMAL,
    STATE_AFTER_TERMINAL,  // After . ? !
    STATE_IN_QUOTE,
    STATE_IN_PARENS
} State;

// Check if a word is a likely abbreviation
int isAbbreviation(const char* word) {
    // Single capital letter (initial)
    if (strlen(word) == 1 && isupper((unsigned char)word[0])) return 1;

    // Common abbreviations
    const char* abbrevs[] = {
        "dr", "mr", "mrs", "ms", "prof", "sr", "jr",
        "st", "ave", "blvd", "no", "vol", "vs",
        "jan", "feb", "mar", "apr", "jun", "jul",
        "aug", "sep", "oct", "nov", "dec", NULL
    };

    char lower[64];
    int i;
    for (i = 0; word[i] && i < 63; i++)
        lower[i] = tolower((unsigned char)word[i]);
    lower[i] = '\0';

    for (int j = 0; abbrevs[j] != NULL; j++) {
        if (strcmp(lower, abbrevs[j]) == 0) return 1;
    }
    return 0;
}

// Extract the last complete word from a buffer (strip trailing punctuation)
void getLastWord(const char* buffer, int len, char* word) {
    word[0] = '\0';
    // Go backwards past punctuation and spaces
    int end = len - 1;
    while (end >= 0 && (ispunct((unsigned char)buffer[end]) || isspace((unsigned char)buffer[end])))
        end--;

    // Now go backwards to find the start of the word
    int start = end;
    while (start > 0 && !isspace((unsigned char)buffer[start - 1]))
        start--;

    if (start <= end) {
        strncpy(word, buffer + start, end - start + 1);
        word[end - start + 1] = '\0';
    }
}

int splitSentences(const char* text, char sentences[][MAX_SENTENCE_LEN]) {
    State state = STATE_NORMAL;
    char buffer[MAX_SENTENCE_LEN];
    int bufLen = 0;
    int sentCount = 0;
    int n = strlen(text);
    char lastWord[64];

    for (int i = 0; i < n; i++) {
        char c = text[i];
        char next = (i + 1 < n) ? text[i + 1] : '\0';
        char nextNext = (i + 2 < n) ? text[i + 2] : '\0';

        buffer[bufLen++] = c;
        buffer[bufLen] = '\0';

        switch (state) {
            case STATE_NORMAL:
                if (c == '"') {
                    state = STATE_IN_QUOTE;
                } else if (c == '(') {
                    state = STATE_IN_PARENS;
                } else if ((c == '.' || c == '?' || c == '!')) {
                    state = STATE_AFTER_TERMINAL;
                }
                break;

            case STATE_AFTER_TERMINAL:
                if (isspace((unsigned char)c) && isupper((unsigned char)next)) {
                    // Potential boundary — check for abbreviation
                    getLastWord(buffer, bufLen - 1, lastWord); // -1 to ignore space
                    if (!isAbbreviation(lastWord)) {
                        // Emit the sentence (up to and including the punctuation)
                        // Trim trailing space
                        int end = bufLen - 1;
                        while (end > 0 && isspace((unsigned char)buffer[end - 1])) end--;
                        buffer[end] = '\0';
                        strncpy(sentences[sentCount++], buffer, MAX_SENTENCE_LEN - 1);
                        bufLen = 0;
                        buffer[0] = '\0';
                        state = STATE_NORMAL;
                    } else {
                        state = STATE_NORMAL;
                    }
                } else if (c == '"') {
                    state = STATE_IN_QUOTE;
                } else if (!isspace((unsigned char)c)) {
                    // Something other than space — back to normal (e.g., "1.5x")
                    state = STATE_NORMAL;
                }
                break;

            case STATE_IN_QUOTE:
                if (c == '"') {
                    state = STATE_NORMAL;
                }
                break;

            case STATE_IN_PARENS:
                if (c == ')') {
                    state = STATE_NORMAL;
                }
                break;
        }
    }

    // Flush remaining text as the last sentence
    if (bufLen > 0) {
        strncpy(sentences[sentCount++], buffer, MAX_SENTENCE_LEN - 1);
    }

    return sentCount;
}

int main() {
    const char* text =
        "Dr. Smith visited D.C. on Monday. "
        "The ratio was 1.5 to 1. It was significant! "
        "He said \"This is fine. Really.\" before leaving. "
        "Ms. Jones (his colleague) agreed. She smiled.";

    char sentences[MAX_SENTENCES][MAX_SENTENCE_LEN];
    int count = splitSentences(text, sentences);

    printf("Found %d sentences:\n\n", count);
    for (int i = 0; i < count; i++) {
        printf("[%d] %s\n", i + 1, sentences[i]);
    }
    return 0;
}

Output:

Found 5 sentences:

[1] Dr. Smith visited D.C. on Monday.
[2] The ratio was 1.5 to 1. It was significant!
[3] He said "This is fine. Really." before leaving.
[4] Ms. Jones (his colleague) agreed.
[5] She smiled.

How the FSM Works — Step by Step

Let's trace through "1.5 to 1. It was" character by character[cite: 1]:

'1'  → STATE_NORMAL,         buffer: "1"
'.'  → STATE_AFTER_TERMINAL, buffer: "1."
'5'  → not space+uppercase → STATE_NORMAL, buffer: "1.5"   ← decimal, no split!
' '  → STATE_NORMAL,         buffer: "1.5 "
't'  → STATE_NORMAL,         buffer: "1.5 t"
...
'1'  → STATE_NORMAL,         buffer: "1.5 to 1"
'.'  → STATE_AFTER_TERMINAL, buffer: "1.5 to 1."
' '  → space! next='I' (uppercase)...
       lastWord = "1" → not an abbreviation!
       EMIT SENTENCE: "1.5 to 1."
       reset buffer, STATE_NORMAL
'I'  → STATE_NORMAL,         buffer: "I"
...

When to Use It

• When you need the most accurate rule-based approach[cite: 1]
• Complex documents: legal contracts, academic papers, news articles[cite: 1]
• When you want fine-grained control over every splitting decision[cite: 1]
• As the foundation for a custom domain-specific splitter[cite: 1]

---

Comparison Table

Method	Speed	Accuracy	Handles Abbrevs	Handles Quotes	Complexity
Naïve Punctuation Split	⚡ Very Fast	❌ Low	❌ No	❌ No	🟢 Trivial
Abbreviation-Aware	⚡ Fast	🟡 Medium	✅ Yes	❌ No	🟡 Easy
Regex Heuristic	⚡ Fast	🟡 Good	✅ Yes	✅ Partial	🟡 Moderate
FSM-Based	🟢 Fast	✅ Best (rule-based)	✅ Yes	✅ Yes	🔴 More Complex

---

Choosing the Right Method

Here's a decision matrix to help choose the best approach for your project[cite: 1]:

---

Tips for Improving Any Rule-Based Splitter

1. Handle ellipses (...) — they rarely end sentences mid-paragraph[cite: 1].
2. Track parenthesis depth — text inside (like this. Really.) should not be split[cite: 1].
3. Handle numbered lists — "1. First item 2. Second item" should not split at 1.[cite: 1].
4. Normalize whitespace first — collapse multiple spaces, replace \t and \n[cite: 1].
5. Post-process short fragments — if a "sentence" is only 1-2 characters, it's probably a false split[cite: 1].

---

Final Thoughts

Sentence splitting is one of those problems that looks trivially easy until you try it on real-world text[cite: 1]. The journey from a one-liner split(".") to a full FSM with state tracking mirrors a broader truth in NLP: language is full of exceptions, and robust systems are built by systematically handling them one by one[cite: 1].

Key Takeaway: Rule-based methods are transparent, fast, and debuggable[cite: 1]. When an FSM makes a wrong call, you can trace the exact logic path and fix it instantly — without retraining a neural model[cite: 1].

That said, for truly noisy or ambiguous text (social media posts, OCR output, multilingual documents), machine learning models will outperform rules[cite: 1]. But for structured documents in a known domain, a well-crafted FSM splitter can be hard to beat[cite: 1].

Happy splitting! 🔪📄

Ternary Search Tree Implementation in C++

A Ternary Search Tree is a trie which leverages concepts of Binary Search Tree as well. A Ternary Search Tree is as memory efficient as Binary Search Trees and time efficient as a Trie.

It is an efficient data structure to store and search large number of strings.

A node in a Ternary Search Tree comprises of these fields :

• Left pointer - Points to Ternary Search Tree containing all strings alphabetically lesser than current node's data
• Right pointer - Points to Ternary Search Tree containing all strings alphabetically greater than current node's data
• Equal pointer - Points to Ternary Search Tree containing all strings alphabetically equal to current node's data
• End of string flag - Flag indicating the end of string
• Data - Actual data in the form of single character

Ternary Search Tree Node

For example, consider adding these strings in the same order into a Ternary Search Tree :

1. "Lead"
2. "Leader"
3. "Leads"
4. "Late"
5. "State"

Let's build a visualization of ternary search tree out of above data :

1. "Lead"
   
2. "Leader"
   
   
3. "Leads"
   
   
4. "Late"
   
   
5. "State"
   

//TST.h
#ifndef TST_H
#define TST_H
//#define DEBUG_PROGRAM_MEMORY

//Node of a Ternary Search Tree
typedef struct TSTNode{
 char data; //Actual data stored in form of character
 bool bEOS; //flag marking end of string
 struct TSTNode* left;   //All character data less than this node
 struct TSTNode* eq;  //All character data equal to this node
 struct TSTNode* right; //All character data greater than this node
}TSTNode;

//Inserts a string in the TST
TSTNode* Insert(TSTNode* root, char* str); 

//Prints all strings in the TST
void PrintAllStringsInTST(TSTNode* root);

//Gets the length of maximum length string in TST
int MaxLenStringLen(TSTNode *root);

//Deleted the complete TST
void DeleteTST(TSTNode *root);

//Search a pattern in TST
bool SearchTST(TSTNode *root, char* pattern);

//Prints 
#ifdef DEBUG_PROGRAM_MEMORY
#include <map>

static std::map<TSTNode*, char> mem_addrs;
void CheckTSTMem();
#endif

#endif

//TST.cpp
#include <iostream>
#define DEBUG_PROGRAM_MEMORY

#include "TST.h"
#include <cstdlib>
#include <utility>

#define MAX_LEN 1024

#define MAX( a, b, c ) ((a)>(b) ? ((a)>(c) ? (a):(c)) : ( (b)>(c) ? (b):(c) ))


TSTNode* Insert(TSTNode* root, char* str)
{
 if(root == NULL)
 {
  root = (TSTNode*)malloc(sizeof(TSTNode));
  if(root == NULL)
  {
   std::cout<<"Memory allocation failed"<<std::endl;
   return NULL;
  }

  //Insert first character of string in the root node
  root->data = *str;
#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.insert(std::make_pair(root, root->data));
#endif
  root->bEOS = false;
  root->left = root->eq = root->right = NULL;
 }
 
 if(*str  < root->data)
  root->left = Insert(root->left, str);
 else if (*str == root->data)
 {
  if(*(str + 1))
   root->eq = Insert(root->eq, str + 1);
  else
   root->bEOS = true;
 }
 else
  root->right = Insert(root->right, str);
 
 return root; 
}

//Helper to print the strings in TST
static void PrintHelper(TSTNode* root, char* buffer, int depth)
{
 if (root)
 {
  // Traverse the left subtree
  PrintHelper(root->left, buffer, depth);

  buffer[depth] = root->data;
  //Once end of string flag is encountered, print the string
  if (root->bEOS)
  {
   buffer[depth + 1] = '\0';
   std::cout<< buffer << std::endl;
  }

  // Traverse the middle subtree
  PrintHelper(root->eq, buffer, depth + 1);

  // Traverse the right subtree
  PrintHelper(root->right, buffer, depth);
 }
}

// Function to print TST's strings
void PrintAllStringsInTST(TSTNode* root)
{
 char buffer[MAX_LEN];
 PrintHelper(root, buffer, 0);
}

bool SearchTST(TSTNode *root, char* pattern)
{
 while (root != NULL)
 {
  if (*pattern < root->data)
   root = root->left;
  else if (*pattern == root->data)
  {
   //If end of string flag is found and the pattern length is also exhausted, 
   //we can safely say that the pattern is present in the TST
   if (root->bEOS && *(pattern + 1) == '\0')
    return true;
   pattern++;
   root = root->eq;
  }
  else
   root = root->right;
 }

 return false;
}

//Function to determine largest 
int MaxLenStringLen(TSTNode *root)
{
 if (root == NULL)
  return 0;

 int leftLen = MaxLenStringLen(root->left);
 int middleLen = MaxLenStringLen(root->eq) + 1;
 int rightLen = MaxLenStringLen(root->right);

 return MAX( leftLen, middleLen, rightLen);
}

void DeleteTST(TSTNode *root)
{
 TSTNode *tmp = root;
 if (tmp)
 {
  DeleteTST(tmp->left);
  DeleteTST(tmp->eq);
  DeleteTST(tmp->right);

#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.erase(tmp);
#endif
  delete tmp;
 }
}

#ifdef DEBUG_PROGRAM_MEMORY
void CheckTSTMem()
{
 std::map<TSTNode*, char>::iterator itr = mem_addrs.begin();

 if (mem_addrs.size() == 0)
 {
  std::cout << "No memory leaks";
  return;
 }

 while (itr != mem_addrs.end()) 
 {
  std::cout << "Memory address " << itr->first<< " for \"" << itr->second << "\" has not been deallocated" << std::endl;
  ++itr;
 }
}
#endif

//Main.cpp
#include <iostream>
#include "TST.h"

int main(int argc, char** argv) {
 
 TSTNode *root = NULL;
 root = Insert(root, "boats");
 root = Insert(root, "boat");
 root = Insert(root, "bat");
 root = Insert(root, "bats");
 root = Insert(root, "stages");

 PrintAllStringsInTST(root);
 std::cout << "Maximum length string in this TST is of size "<< MaxLenStringLen(root) << std::endl;

 char *str = "hello";
 char *str1 = "bat";

 if (SearchTST(root, str) == false)
  std::cout << "\""<<str<<"\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str << "\" is present in TST" << std::endl;

 if (SearchTST(root, str1) == false)
  std::cout << "\"" << str << "\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str1 << "\" is present in TST" << std::endl;

 DeleteTST(root);

#ifdef DEBUG_PROGRAM_MEMORY
 CheckTSTMem();
#endif
 
 return 0;
}