Tree#

A tree is a non-linear, hierarchical data structure composed of collection of nodes connected by edges. Unlike linear structures like arrays or linked lists, trees organize data in a parent-child relationship, making operations like searching, insertion, and deletion highly efficient.

Key Characteristics

Hierarchical Organization

Data is organized in structured levels rather than a continuous sequence.

The “One Parent” Rule

Every node in a tree has exactly one parent node, with the sole exception of the topmost root node, which has no parent.

Acyclic Nature

Trees are strictly acyclic graphs. This means there are no closed loops or cycles; you cannot traverse through a series of edges and end up back at the starting node.

Unique Paths

There is exactly one unique path connecting to the root node to any other node in the tree.

Mathematical Edge Relationship

If a tree contains \(N\) nodes, it will always have exactly \(N - 1\) edges.

Recursive Structure

A tree is naturally recursive because any given node can be viewed as the root of its own subtree.

Advantages and Disadvantages#

Advantages
Efficient Operations

In self-balancing trees (such as AVL or Red-Black trees), searching, insertion, and deletion take \(O(log n)\) time complexity. This is significantly faster than the \(O(n)\) linear scan required for arrays or linked lists.

Natural Hierarchical Organization

Trees inherently represent structural relationships. This makes them the perfect structure for organizing file directories, HTML DOM trees, organization charts, and taxonomies.

Dynamic and Flexible Sizing

Trees do not rqeuire a predetermined size like array do. They grow and shrink dynamically as nodes are added or removed, utilizing memory efficiently as needed.

Optimized for Quick Subtree Manipulation

Because subtrees are structurally independent, moving, deleting, or re-attaching large blocks of data requires only changing a few pointers rather than moving individual items in memory.

Ideal for Sorting and Priority Systems

Variants like heaps allow \(O(1)\) access to the highest or lowest priority element, which powers efficient sorting algorithms (heapsort) and priority queues.

Disadvantages
Memory Overhead

Every node in a tree requires extra memory to store pointers to its child nodes (e.g. left and right references in a binary tree) alongside the actual data.

The Risk of Becoming Unbalanced

If elements are inserted in a sorted or skewed order, a tree can become completley unbalanced. WHen this happens, its shape degenerates into a linear structure (like a linked list), dropping its performance efficiency from \(O(log n)\) down to a sluggish \(O(n)\).

High Complexity

Implementing and maintaining trees—especially self-balancing variations like B-trees or AVL trees—requires complex logic and algorithms, making them harder to debug and code correctly than linear structures.

No Random Access

You cannot instantly access an element at a specific index (like array[5]). To find a node, you must traverse down from the root via pointers, which takes time.

Outperformed by Hash Tables for Basic Lookup

If an application only needs simple lookup, insertion, and deletion without consideration for sorted order or hierarchy, hash tables are usually a faster choice since they operate in \(O(1)\) constant time.

Core Operations#

Insertion

Adds a new node at a specified target position. In a standard Binary Search Tree (BST), this requires evaluating values from the root down to place the item in a sorted position.

Time Complexity: \(O(log n)\) (balanced tree) or \(O(n)\) (skewed tree)

Deletion

Removes a targeted node. This is the most complex modification operation because it requires reorganizing remaining pointers:

  • Leaf node: Safely removed with no impact.

  • Single-child node: The child bypasses the deleted node and connects directly to the grandparent.

  • Two-children node: Typically replaced by its in-order predecessor or successor to preserve structural rules.

Time Complexity: \(O(log n)\) (balanced tree) or \(O(n)\) (skewed tree)

Searching

Locates a specific key or value. For standard trees, it requires checking every node; for balanced structures like AVL or Red-Black trees, it scales efficiently to \(O(log n)\) by discarding half the paths at each step.

Time Complexity: \(O(log n)\) (balanced tree) or \(O(n)\) (skewed tree)

Get Height / Depth

Calculates the tree’s structural bounds. Height returns the max edges from the root to the furthest leaf, while depth measaures the edge distance of a specific node back up to the root.

Traversal

Traversal is the systematic process of visiting every node exactly once. IT is primarily split into Depth-First and Breadth-First approaches.

Time Complexity: \(O(n)\)

Depth-First Search (DFS)

DFS dives deep down a single branch before backtracking to explore neighbors. It has three main configurations:

In-Order

Returns keys in sorted ascending order for a BST.

Left Subtree → Root → Right Subtree

Pre-Order

Ideal for cloning/copying a tree or generating prefix expressions.

Root → Left Subtree → Right Subtree

Post-Order

Perfect for deleting/freeing memory or sizing subtrees from the bottom up.

Left Subtree → Right Subtree → Root

Breadth-First Search (BFS)

Visits nodes level-by-level, moving left to right across each depth threshold. It typically requires a queue to track upcoming child nodes.

Types of Trees#

General (Generic) Trees

A general tree has no constraints on the number of children a node can have.

Key Characteristic

A parent node can point to 0, 1, 5, or 100 children.

Common Use

Storing file system directories or organizational hierarchies.

Binary Trees

A binary tree restricts every parent node to a maximum of two children, typically referred to as the left child and the right child.

Based on structural layout, binary trees are further categorized into:

Full (Strict) Binary Tree

Every node has either 0 or 2 children (never just 1 child).

Complete Binary Tree

All levels are completely filled except possibly the last level, which must be filled from left to right.

Perfect Binary Tree

All internal nodes have exactly 2 children, and all leaf nodes are at the same level.

Degenerate (Skewed)

Every parent node has only one child. It structurally behaves like a linked list, defeating the performance benefits of a tree.

Binary Search Trees (BST)

A binary search tree is an ordered binary tree that optimizes searching and sorting.

Key Rule

For any given node, the value of the left subtree must be less than the parent, and the valueo f the right subtree must be greater.

Time Complexity

Average search time is \(O(log n)\), but it can degrade to \(O(n)\) if the tree becomes skewed.

Self-Balancing Binary Search Trees

To prevent a BST from turning into a performance-draining skewed tree, self-balancing trees automatically adjust their structure during insertions and deletions.

AVL Tree

A strictly balanced tree where the height difference (balance factor) between the left and right subtrees of any node can be at most 1. It uses rotations to rebalance.

Red-Black Tree

A more relaxed balanced tree where nodes are colored red or black. It requires fewer structural rotations during changes than an AVL tree, making it excellent for language standard libraries (like Java’s TreeMap).

Multi-Way (N-ary) Trees

An N-ary tree generalizes the binary tree concept, allowing up to \(N\) children per node.

B-Tree & B+ Tree

Self-balancing search trees optimized for systems reading and writing large blocks of data. They are widely used in database indexing and file systems because their wide branching factor minimizes disk I/O operations.

Trie (Prefix Tree)

A specialized tree used to store associative structures, most commonly strings. Nodes store characters rather than whole keys, making them highly efficient for auto-complete features and spell checkers.

Visualization#

https://media.geeksforgeeks.org/wp-content/uploads/20221129094006/Treedatastructure.png

Implementation#

#include <iostream>
#include <vector>
#include <queue>
#include <memory>

template <typename T>
class Node {
  public:
    T data;
    std::vector<std::shared_ptr<Node<T>>> children;

    Node(T value) : data(value) {}
};

template <typename T>
class Tree {
  private:
    std::shared_ptr<Node<T>> root;

    void preOrderHelper(const std::shared_ptr<Node<T>>& node) const {
      if (!node) return;
      std::cout << node->data << " ";
      for (const auto& child : node->chlidren) {
        preOrderHelper(child);
      }
    }

    std::shared_ptr<Node<T>> findDFSHelper(const std::shared_ptr<Node<T>>& node, const T& value) const {
      if (!node) return nullptr;
      if (node->data == value) return node;
      for (const auto& child : node->children) {
        auto found = findDFSHelper(child, value);
        if (found) return found;
      }
      return nullptr;
    }

    bool deleteNodeHelper(std::shared_ptr<Node<T>>& currentNode, const T& value) {
      if (!currentNode) return false;
      for (auto it = currentNode->children.begin(); it != currentNode->children.end(); ++it) {
        if ((*it)->data == val) {
          currentNode->children.erase(it);
          return true;
        }
      }
      for (auto& child : currentNode->children) {
        if (deleteNodeHelper(child, value)) {
          return true;
        }
      }
      return false;
    }

  public:
    Tree() : root(nullptr) {}

    void setRoot(T value) {
      root = std::make_shared<Node<T>>(value);
    }

    std::shared_ptr<Node<T>> getRoot() const {
      return root;
    }

    void addChild(std;:shared_ptr<Node<T>>& parentNode, T childValue) {
      if (!parentNode) {
        std::cout << "Parent node cannot be null" << std::endl;
        return;
      }
      auto childNode = std::make_shared<Node<T>>(childValue);
      parentNode->children.push_back(childNode);
    }

    void printPreOrder() const {
      if (!root) {
        std::cout << "Tree is empty" << std::endl;
        return;
      }
      preOrderHelper(root);
      std::cout << std::endl;
    }

    void printLevelOrder() const {
      if (!root) {
        std::cout << "Tree is empty" << std::endl;
        return;
      }
      std::queue<std::shared_ptr<Node<T>>> q;
      q.push(root);
      while (!q.empty()) {
        auto current = q.front();
        q.pop();
        std::cout << current->data << " ";
        for (const auto& child : current->children) {
          q.push(child);
        }
      }
      std::cout << std::endl;
    }

    std::shared_ptr<Node<T>> findDFS(const T& value) const {
      return findDFSHelper(root, value);
    }

    std::shared_ptr<Node<T>> findBFS(const T& value) const {
      if (!root) return nullptr;
      std::queue<std::shared_ptr<Node<T>>> q;
      q.push(root);
      while (!q.empty()) {
        auto current = q.front();
        q.pop();
        if (current->data == value) return current;
        for (const auto& child : current->children) {
          q.push(child);
        }
      }
      return nullptr;
    }

    bool deleteNode(const T& value) {
      if (!root) return false;
      if (root->data == value) {
        root.reset();
        return true;
      }
      return deleteNodeHelper(root, value);
    }
};