BST Class Reference

Iterative binary search tree storing integer values. More...

#include <BST.h>

Public Member Functions
	BST ()
	Constructs an empty BST.
	~BST ()
	Destroys the BST and frees all dynamically allocated nodes.
void	insert (int value)
	Inserts a value into the BST.
bool	search (int value) const
	Searches for a value in the BST.
void	inorder () const
	Performs an inorder traversal of the tree.
void	levelOrder () const
	Performs a level-order (breadth-first) traversal of the tree.
bool	remove (int value)
	Removes a value from the BST if it exists.

Detailed Description

Iterative binary search tree storing integer values.

The BST class is an iterative, pointer-based binary search tree implementation using raw pointers and manual dynamic memory management. The BST owns all allocated nodes and is responsible for their cleanup through its destructor.

The BST class manages dynamically allocated Node objects, forming a binary search tree structure. All operations, including insert, search, delete, and traversal, are implemented iteratively to avoid recursion.

The tree maintains standard BST ordering properties:

• Left subtree contains values less than the node.
• Right subtree contains values greater than the node.
• Duplicate values are ignored.

Memory Management: The BST owns all its nodes. The destructor invokes a private destroyTree() helper method, ensuring that all nodes are properly freed and preventing memory leaks.

See also

Node

Definition at line 50 of file BST.h.

Constructor & Destructor Documentation

BST()

BST::BST

(

)

Constructs an empty BST.

Initializes the BST root pointer to nullptr.

Definition at line 26 of file BST.cpp.

: root(nullptr) {}

~BST()

BST::~BST

(

)

Destroys the BST and frees all dynamically allocated nodes.

Calls destroyTree() to deallocate all nodes in the tree.

Definition at line 31 of file BST.cpp.

          {
    destroyTree();
}

Member Function Documentation

inorder()

void BST::inorder

(

)

const

Performs an inorder traversal of the tree.

Prints node values in ascending order using an iterative traversal.

Traverses the tree in-order using an iterative approach.

Uses an explicit stack to traverse the tree without recursion and prints values in ascending order.

Definition at line 102 of file BST.cpp.

                        {
    if (!root) return;
 
    Stack s;
    Node* current = root;
 
    while (current || !s.isEmpty()) {
        while (current) {
            s.push(current);
            current = current->getLeft();
        }
 
        current = s.pop();
        std::cout << current->getValue() << " ";
        current = current->getRight();
    }
 
    std::cout << std::endl;
}

insert()

void BST::insert

(

int

value

)

Inserts a value into the BST.

Parameters

value

The integer value to insert.

Note

Duplicate values are ignored.

Iteratively inserts a value into the BST.

The tree is traversed from the root to locate the appropriate insertion point. Duplicate values are detected and ignored to preserve BST invariants.

Definition at line 41 of file BST.cpp.

                          {
    Node* newNode = new Node(value);
 
    // Special case: empty tree
    if (!root) {
        root = newNode;
        return;
    }
 
    Node* current = root;
    Node* parent = nullptr;
 
    // Traverse the tree to find the insertion point
    while (current) {
        parent = current;
 
        if (value < current->getValue())
            current = current->getLeft();
        else if (value > current->getValue())
            current = current->getRight();
        else {
            // Duplicate value detected; discard new node
            delete newNode;
            return;
        }
    }
 
    // Attach the new node to its parent
    if (value < parent->getValue())
        parent->setLeft(newNode);
    else
        parent->setRight(newNode);
}

levelOrder()

void BST::levelOrder

(

)

const

Performs a level-order (breadth-first) traversal of the tree.

Visits nodes level by level (breadth-first traversal).

Uses a queue to visit nodes level by level starting from the root.

Definition at line 127 of file BST.cpp.

                           {
    if (!root) return;
 
    Queue q;
    q.enqueue(root);
 
    while (!q.isEmpty()) {
        Node* current = q.dequeue();
        std::cout << current->getValue() << " ";
 
        if (current->getLeft())
            q.enqueue(current->getLeft());
        if (current->getRight())
            q.enqueue(current->getRight());
    }
 
    std::cout << std::endl;
}

remove()

bool BST::remove

(

int

value

)

Removes a value from the BST if it exists.

Parameters

value

The value to remove.

Returns

true if the value was found and removed; otherwise false.

Deletes the specified value if it exists in the BST.

Handles all three standard BST deletion cases:

1. Node is a leaf
2. Node has one child
3. Node has two children (using inorder successor replacement)

Definition at line 154 of file BST.cpp.

                          {
    Node* parent = nullptr;
    Node* current = root;
 
    // Locate the node to delete
    while (current && current->getValue() != value) {
        parent = current;
        if (value < current->getValue())
            current = current->getLeft();
        else
            current = current->getRight();
    }
 
    if (!current)
        return false; // Value not found
 
    // ------------------------------------------------------------
    // Case 1: Node has no children (leaf)
    // ------------------------------------------------------------
    if (!current->getLeft() && !current->getRight()) {
        if (current == root)
            root = nullptr;
        else if (parent->getLeft() == current)
            parent->setLeft(nullptr);
        else
            parent->setRight(nullptr);
 
        delete current;
    }
 
    // ------------------------------------------------------------
    // Case 2: Node has exactly one child
    // ------------------------------------------------------------
    else if (!current->getLeft() || !current->getRight()) {
        Node* child = current->getLeft()
            ? current->getLeft()
            : current->getRight();
 
        if (current == root)
            root = child;
        else if (parent->getLeft() == current)
            parent->setLeft(child);
        else
            parent->setRight(child);
 
        delete current;
    }
 
    // ------------------------------------------------------------
    // Case 3: Node has two children
    // ------------------------------------------------------------
    else {
        // Find inorder successor (leftmost node in right subtree)
        Node* succParent = current;
        Node* successor = current->getRight();
 
        while (successor->getLeft()) {
            succParent = successor;
            successor = successor->getLeft();
        }
 
        // Replace current node's value with successor's value
        current->setValue(successor->getValue());
 
        // Remove successor node (which has at most one child)
        Node* child = successor->getRight();
 
        if (succParent->getLeft() == successor)
            succParent->setLeft(child);
        else
            succParent->setRight(child);
 
        delete successor;
    }
 
    return true;
}

search()

bool BST::search

(

int

value

)

const

Searches for a value in the BST.

Parameters

value

The value to search for.

Returns

true if the value exists in the tree; otherwise false.

Iteratively searches for a value in the BST.

Traverses the tree according to BST ordering rules until the value is found or a null pointer is reached.

Definition at line 81 of file BST.cpp.

                                {
    Node* current = root;
 
    while (current) {
        if (value == current->getValue())
            return true;
        else if (value < current->getValue())
            current = current->getLeft();
        else
            current = current->getRight();
    }
 
    return false;
}

---

The documentation for this class was generated from the following files:

• BST.h
• BST.cpp