binary-search-tree.cc

/*
 * Binary Search Tree (BST) Concepts and Operations
 *
 * A Binary Search Tree (BST) is a binary tree where:
 * 1. The left subtree of a node contains only nodes with keys less than the node's key.
 * 2. The right subtree of a node contains only nodes with keys greater than the node's key.
 * 3. Both the left and right subtrees must also be binary search trees.
 *
 * Operations on Binary Search Tree:
 *
 * 1. Insertion:
 *    - Description: Adds a new node with a specified key to the BST.
 *    - Time Complexity: O(h), where h is the height of the tree.
 *    - Space Complexity: O(1) for iterative insertion; O(h) for recursive insertion (due to recursion stack).
 *
 * 2. Deletion:
 *    - Description: Removes a node with a specified key from the BST.
 *    - Time Complexity: O(h), where h is the height of the tree.
 *    - Space Complexity: O(1) for iterative deletion; O(h) for recursive deletion.
 *
 * 3. Search:
 *    - Description: Searches for a node with a specified key in the BST.
 *    - Time Complexity: O(h), where h is the height of the tree.
 *    - Space Complexity: O(1) for iterative search; O(h) for recursive search.
 *
 * 4. Traversal:
 *    - Description: Visits all the nodes in the BST in a specific order.
 *    - Types of Traversal:
 *      a. In-order (Left, Node, Right): Yields sorted order of keys.
 *      b. Pre-order (Node, Left, Right): Useful for creating a copy of the tree.
 *      c. Post-order (Left, Right, Node): Useful for deleting the tree.
 *      d. Level order:
 *         - Description: Traverses the tree level by level from top to bottom.
 *         - Time Complexity: O(n), where n is the number of nodes in the tree.
 *         - Space Complexity: O(n) for using a queue to store nodes at each level.
 *    - Time Complexity: O(n), where n is the number of nodes in the tree.
 *    - Space Complexity: O(h) for recursive traversal; O(n) for iterative traversal using a stack.
 *
 * 5. Finding Minimum and Maximum:
 *    - Description: Finds the node with the minimum or maximum key in the BST.
 *    - Time Complexity: O(h), where h is the height of the tree.
 *    - Space Complexity: O(1).
 *
 * 6. Checking if a tree is a BST:
 *    - Description: Validates if a binary tree is a BST.
 *    - Time Complexity: O(n), where n is the number of nodes in the tree.
 *    - Space Complexity: O(h) for recursive validation; O(1) for iterative validation.
 *
 * 8. Height of BST:
 *    - Description: Calculates the height of the BST.
 *    - Time Complexity: O(n), where n is the number of nodes in the tree.
 *    - Space Complexity: O(h) for recursive height calculation; O(1) for iterative.
 *
 * 9. Depth of a Node:
 *    - Description: Calculates the depth of a specific node in the BST.
 *    - Time Complexity: O(h), where h is the height of the tree (in the worst case, it can be O(n)).
 *    - Space Complexity: O(1) for iterative implementation; O(h) for recursive implementation.
 *
 * 10. Range Search:
 *    - Description: Finds all keys within a given range [low, high].
 *    - Time Complexity: O(k + h), where k is the number of keys in the range, and h is the height of the tree.
 *    - Space Complexity: O(h) for recursive implementation; O(1) for iterative implementation.
 *
 * 11. Lowest Common Ancestor (LCA):
 *    - Description: Finds the lowest common ancestor of two nodes in the BST.
 *    - Time Complexity: O(h), where h is the height of the tree.
 *    - Space Complexity: O(1) for iterative implementation; O(h) for recursive implementation.
 *
 * Notes:
 * - The height of a balanced BST is O(log n), while the height of an unbalanced BST can be O(n) in the worst case.
 * - BST operations can be optimized by keeping the tree balanced.
 */

// put binary search tree in file for persistence, ER Diagram

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#include <tuple>
#include <inttypes.h>
#include <limits>

struct Node {
  uint8_t key;
  std::string name;
  struct Node* left;
  struct Node* right;

  Node(uint8_t key, std::string name, struct Node* left, struct Node* right):
  	key(key), name(name), left(nullptr), right(nullptr) {}
};

struct BinarySearchTree {
private:
  struct Node* root;

  Node* search_node(uint8_t key) {
    return root;
  }
public:
  BinarySearchTree() : root(nullptr) {}

  ~BinarySearchTree() {
    if (root) {
      std::stack<Node*> st;

      st.push(root);
      while (!st.empty()) {
        Node *current = st.top();
        st.pop();

        if (current->right)
          st.push(current->right);
        if (current->left)
          st.push(current->left);

        delete current;
      }
    }
  }

  void insert(uint8_t key, std::string name) {
    struct Node* newNode = new Node(key, name, nullptr, nullptr);

    if (root == nullptr) {
      root = newNode;
      return;
    }

    struct Node* node = root;
    while (node) {
      if (node->key > key) {
        if (node->left == nullptr) {
          node->left = newNode;
          break;
        }
        node = node->left;
      } else {
        if (node->right == nullptr) {
          node->right = newNode;
          break;
        }
        node = node->right;
      }
    }
  }

  Node* search(uint8_t key) {
    struct Node* node = root;

    while (node) {
      if (node->key == key) {
        return node;
      }

      if (node && node->key > key) {
        node = node->left;
      } else if (node && node->key < key) {
        node = node->right;
      }
    }

    return node;
  }

  std::vector<uint8_t> searchRange(uint8_t low, uint8_t high) {
    std::vector<uint8_t> list;
    std::queue<Node*> queue;

    if (!root)
      return list;

    queue.push(root);

    while (!queue.empty()) {
      struct Node *current = queue.front();
      queue.pop();

      if (low <= current->key && high >= current->key)
        list.push_back(current->key);

      if (current->left)
        queue.push(current->left);
      if (current->right)
        queue.push(current->right);
    }

    return list;
  }

  std::vector<uint8_t> preorder() {
    if (root == nullptr)
      return  {};

    std::vector<uint8_t> preorder_vector;
    std::stack<Node *> stack;

    stack.push(root);
    while (!stack.empty()) {
      struct Node *current = stack.top();
      stack.pop();

      while (current) {
        if (current->right)
          stack.push(current->right);

        preorder_vector.push_back(current->key);
        current = current->left;
      }
    }

//    while (!stack.empty()) {
//      struct Node *current = stack.top();
//      stack.pop();
//      preorder_vector.push_back(current->key);
//      if (current->right != nullptr)
//        stack.push(current->right);
//      if (current->left != nullptr)
//        stack.push(current->left);
//    }

    return preorder_vector;
  }

  std::vector<uint8_t> inorder() {
    std::vector<uint8_t> inorder_vector;
    std::stack<struct Node*> stack;
    struct Node* current = root;

    while (!stack.empty() || current) {
      while (current) {
        stack.push(current);
        current = current->left;
      }

      current = stack.top();
      stack.pop();
      inorder_vector.push_back(current->key);
      current = current->right;
    }

    return inorder_vector;
  }

  std::vector<uint8_t> postorder() {
    if (!root)
      return {};

    std::vector<uint8_t> postorder_vector;
    std::stack<Node *> stack1;
    std::stack<Node *> stack2;

    stack1.push(root);

    while (!stack1.empty()) {
      struct Node* node = stack1.top();
      stack2.push(node);
      stack1.pop();

      if (node->left)
        stack1.push(node->left);
      if (node->right)
        stack1.push(node->right);
    }

    while (!stack2.empty()) {
      struct Node* curr = stack2.top();
      stack2.pop();

      postorder_vector.push_back(curr->key);
    }

    return postorder_vector;
  }

  std::vector<uint8_t> levelorder() {
    std::vector<uint8_t> levelorder_vector;
    std::queue<Node*> queue;

    if (root)
      queue.push(root);

    while (!queue.empty()) {
      struct Node* node = queue.front();
      queue.pop();

      if (node->left)
        queue.push(node->left);
      if (node->right)
        queue.push(node->right);

      levelorder_vector.push_back(node->key);
    }

    return levelorder_vector;
  }

  std::vector<uint8_t> findMinMax() {
    std::stack<Node*> stack;

    uint8_t min = std::numeric_limits<uint8_t>::max();
    uint8_t max = std::numeric_limits<uint8_t>::min();

    if (root)
      stack.push(root);

    while (!stack.empty()) {
      struct Node *current = stack.top();
      stack.pop();

      if (min > current->key)
        min = current->key;
      if (max < current->key)
        max = current->key;

      if (current->left)
        stack.push(current->left);
      if (current->right)
        stack.push(current->right);
    }

    return {min, max};
  }

  uint8_t LCA(uint8_t r, uint8_t l) {
    Node *current = root;

    while (current) {
      if (current->key > r && current->key > l) {
        current = current->left;
      } else if (current->key < r && current->key < l) {
        current = current->right;
      } else {
        return current->key;
      }
    }

    return 0;
  }

  int height() {
    if (!root)
      return -1;

    std::queue<std::pair<int, Node*>> queue;
    int hgt = 0;
    queue.push({0, root});

    while (!queue.empty()) {
      auto front = queue.front();
      queue.pop();
      Node *current = front.second;
      int h = front.first;

      if (current->left)
        queue.push({h + 1, current->left});

      if (current->right)
        queue.push({h + 1, current->right});

      hgt = std::max(hgt, h);
    }

    return hgt;
  }

  bool is_bst() {
    if (!root)
      return true;

    std::stack<std::tuple<Node*, uint8_t, uint8_t>> st;

    st.push({
        root,
        std::numeric_limits<uint8_t>::min(),
        std::numeric_limits<uint8_t>::max(),
    });

    while (!st.empty()) {
      auto [current, min, max] = st.top();
      st.pop();

      if (current->key >= max || current->key <= min) {
          return false;
      }

      if (current->left)
        st.push({current->left, min, current->key});

      if (current->right)
        st.push({current->right, current->key, max});
    }

    return true;
  }

  bool delete_node(uint8_t key) {
    Node *current = root;
    Node *parent = nullptr;

    while (current != nullptr && current->key != key) {
      parent = current;
      if (current->key < key) {
        current = current->right;
      } else {
        current = current->left;
      }
    }

    if (!current)
      return false;

    if (!current->left && !current->right) {
      // case 1: leaf node

      if (!parent) {
        root = nullptr;
      } else if (parent->left == current) {
        parent->left = nullptr;
      } else {
        parent->right = nullptr;
      }

      delete current;
    } else if (!current->right || !current->left) {
      // case 2: have one node

      Node *child = current->left ? current->left : current->right;

      if (!parent) {
        root = child;
      } else if (parent->left == current) {
        parent->left = child;
      } else {
        parent->right = child;
      }

      delete current;
    } else {
      // case 3: two nodes

      Node *successor = current->right;
      Node *successorParent = current;

      while (successor->left) {
        successorParent = successor;
        successor = successor->left;
      }

      current->key = successor->key;
      current->name = successor->name;

      if (successorParent->left == successor) {
        successorParent->left = successor->right;
      } else {
        successorParent->right = successor->right;
      }

      delete successor;
    }

    return true;
  }
};

int main() {
  BinarySearchTree bst;
  std::vector<uint8_t> order;

  std::vector<std::pair<uint8_t, std::string>> vec = {
      {8, "John"},
      {15, "Tesla"},
      {3, "Curie"},
      {2, "Bjarne Stroustrup"},
      {12, "Einstein"},
      {10, "Eratosthenes"},
      {20, "Newton"},
      {19, "Sieve"},
      {7, "Strif"},
      {6, "Bill"},
      {5, "Martan"},
      {21, "James Gosling"},
      {22, "James Gosling"},
  };

//  vec = {
//    {8, "John"},
//    {15, "Tesla"},
//    {3, "Curie"},
//    {2, "Bjarne Stroustrup"},
//    {12, "Einstein"},
//    {10, "Eratosthenes"},
//    {20, "Newton"},
//    {19, "Sieve"},
//    {7, "Strif"},
//    {6, "Bill"},
//    {5, "Martan"},
//    {21, "James Gosling"},
//    {1, "Ada Lovelace"},
//    {9, "Alan Turing"},
//    {4, "Grace Hopper"},
//    {18, "Nikola Tesla"},
//    {25, "Tim Berners-Lee"},
//    {17, "Guido van Rossum"},
//    {13, "Dennis Ritchie"},
//    {11, "Linus Torvalds"},
//    {22, "Donald Knuth"},
//    {14, "Ken Thompson"},
//    {24, "Richard Stallman"},
//    {16, "Barbara Liskov"},
//    {23, "Marissa Mayer"},
//    {26, "Margaret Hamilton"}
//  };

//  vec = {
//      {4, "Root"},
//      {2, "Left Child"},
//      {6, "Right Child"},
//      {1, "Left Leaf"},
//      {3, "Right Leaf"},
//      {7, "Right Leaf of 6"},
//  };

  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << static_cast<int>(it->first) << ", ";
    bst.insert(it->first, it->second);
  }
  std::cout << std::endl;

//  for (auto it = vec.begin(); it != vec.end(); ++it) {
//    std::cout << static_cast<int>(it->first) << ", ";
//    bst.delete_node(it->first);
//  }

  bst.delete_node(21);

  Node *search = bst.search(10);
  if (search != nullptr) {
    std::cout << "Founded Node: " << static_cast<int>(search->key) << "->" << search->name << std::endl;
  }

  std::cout << "preorder:\n";
  order = bst.preorder();
  for (const uint8_t& data : order) {
    std::cout << static_cast<int>(data) << ", ";
  }

  std::cout << std::endl;

  std::cout << "inorder:\n";
  order = bst.inorder();
  for (const uint8_t& data : order) {
    std::cout << static_cast<int>(data) << ", ";
  }

  std::cout << std::endl;

  std::cout << "postorder:\n";
  order = bst.postorder();
  for (const uint8_t& data : order) {
    std::cout << static_cast<int>(data) << ", ";
  }

  std::cout << std::endl;

  std::cout << "levelorder:\n";
  order = bst.levelorder();
  for (const uint8_t& data : order) {
    std::cout << static_cast<int>(data) << ", ";
  }

  std::cout << std::endl;

  std::cout << "findMinMax:\n";
  order = bst.findMinMax();
  std::cout << static_cast<int>(order[0]) << ", ";
  std::cout << static_cast<int>(order[1]) << ", ";

  std::cout << std::endl;

  std::cout << "searchRange:\n";
  order = bst.searchRange(4, 10);
  for (const uint8_t& data : order) {
    std::cout << static_cast<int>(data) << ", ";
  }

  std::cout << std::endl;

  std::cout << "Lowest Common Ancestor (LCA):\n";
  std::cout << static_cast<int>(bst.LCA(10, 21));

  std::cout << std::endl;

  std::cout << "Height:\n";
  std::cout << static_cast<int>(bst.height());

  std::cout << std::endl;

  std::cout << "Is BST:\n";
  std::cout << static_cast<int>(bst.is_bst());

  std::cout << std::endl;

  return 0;
}

binary-tree.cc

/**
 * Binary Tree:
 * - A binary tree is a type of tree data structure in which each node has at most two children or degree,
 *      referred to as the left child and the right child.
 * - In a binary tree, each node can have zero, one, or two children.
 * - Binary trees are used in various applications such as binary search trees, expression trees, and binary heaps.
 * - Binary trees can be traversed in different ways, including in-order, pre-order, post-order and level traversal.
 *
 *                    1
 *                  /   \
 *                 /     \
 *                /       \
 *               /         \
 *              2           3
 *             / \         / \
 *            /   \       /   \
 *           /     \     /     \
 *          4       5   6       7
 *         / \     /
 *        8   9   10
 *
 * if Level order is: 1 2 3 4 5 6 7 8 9 10
 *
 * Expected Pre-order:
 *  Root -> Left -> Right
 *  1 2 4 8 9 5 10 3 6 7
 *
 * Expected In-order:
 *  Left -> Root -> Right
 *  8 4 9 2 10 5 1 6 3 7
 *
 * Expected Post-order:
 *  Left -> Right -> Root
 *  8 9 4 10 5 2 6 7 3 1
 */

#include "iostream"
#include "vector"
#include "stack"
#include "queue"

struct Node {
    unsigned int item;
    Node *left;
    Node *right;

    explicit Node(unsigned int item, Node *left = nullptr, Node *right = nullptr) :
            item(item), left(left), right(right) {};
};

void print(const std::vector<int> &items) {
    for (int i: items)
        std::cout << i << ' ';

    std::cout << std::endl;
}

class BinaryTree {
private:
    Node *m_head;
public:
    BinaryTree() {
        m_head = nullptr;
    }

    ~BinaryTree() {}

    void insert(unsigned int item) {
        Node *node = new Node(item);
        Node *tmp = nullptr;
        std::queue<Node *> q;

        if (!m_head) {
            m_head = node;
            return;
        }

        q.push(m_head);

        while (!q.empty()) {
            tmp = q.front();
            q.pop();

            if (tmp->left)
                q.push(tmp->left);

            if (tmp->right)
                q.push(tmp->right);

            if (tmp->left == nullptr) {
                tmp->left = node;
                break;
            } else if (tmp->right == nullptr) {
                tmp->right = node;
                break;
            }
        }
    }

    bool is_complete() {
        if (!m_head)
            return true;

        std::stack<Node*> st;
        st.push(m_head);

        while (!st.empty()) {
            Node *tmp = st.top();
            st.pop();

            if (tmp->left != NULL && tmp->right == NULL)
                return false;

            if (tmp->right)
                st.push(tmp->right);

            if (tmp->left)
                st.push(tmp->left);
        }

        return true;
    }

    bool is_almost_complete() {
        if (!m_head)
            return true;

        std::stack<Node*> st;
        st.push(m_head);

        while (!st.empty()) {
            Node *tmp = st.top();
            st.pop();

            if (tmp->left == nullptr && tmp->right != nullptr)
                return false;

            if (tmp->right)
                st.push(tmp->right);

            if (tmp->left)
                st.push(tmp->left);
        }

        return true;
    }

    /**
     * Level: The level of a node in a tree refers to its distance from the root node, where the root node is considered to be at level 0.
     * Each subsequent level represents a generation of nodes, with the children of the nodes at the previous level.
     * In other words, all nodes at a given level are at the same distance from the root node.
     * 
     * For example, consider the following tree:
     *       1
     *     /   \
     *    2     3
     *   / \   / \
     *  4   5 6   7
     * In this tree:
     * The root node (1) is at level 0.
     * Nodes 2 and 3 are at level 1.
     * Nodes 4, 5, 6, and 7 are at level 2.
     *
     * Height: The height of a tree, on the other hand, refers to the number of edges between the root node and the furthest leaf node.
     * In other words, it's the maximum distance from the root node to any leaf node.
     * The height of this tree is 2, because the longest path from the root node (1) to a leaf node (4, 5, 6, or 7) has 2 edges.
     *
     * Key differences:
     * - Level is a property of a specific node, while height is a property of the entire tree.
     * - Level measures the distance from the root node to a specific node, while height measures the maximum distance from the root node to any leaf node.
     *
     * @return
     */
    int get_level(int find) {
        if (!m_head)
            return -1;

        std::queue<std::pair<Node *, int>> queue;
        queue.emplace(m_head, 0);

        while (!queue.empty()) {
            Node *tmp = queue.front().first;
            int l = queue.front().second;
            queue.pop();

            if (tmp->item == find)
                return l;

            if (tmp->right)
                queue.emplace(tmp->right, l + 1);

            if (tmp->left)
                queue.emplace(tmp->left, l + 1);
        }

        return -1;
    }

    int get_height() {
        if (!m_head)
            return 0;

        int maxHeight = 0;
        std::queue<std::pair<Node *, int>> q;

        q.emplace(m_head, 0);

        while (!q.empty()) {
            Node *tmp = q.front().first;
            int level = q.front().second;
            q.pop();

            maxHeight = std::max(maxHeight, level);

            if (tmp->right) {
                q.emplace(tmp->right, level + 1);
            }

            if (tmp->left) {
                q.emplace(tmp->left, level + 1);
            }
        }

        return maxHeight;
    }

    bool delete_node() {
        return false;
    }

    bool search(unsigned int find) {
        if (!m_head)
            return {};

        std::stack<Node *> st;
        Node *tmp = nullptr;

        st.push(m_head);

        while (!st.empty()) {
            tmp = st.top();
            st.pop();

            if (tmp->item == find)
                return true;

            if (tmp->left)
                st.push(tmp->left);

            if (tmp->right)
                st.push(tmp->right);
        }

        return false;
    }

    std::vector<int> get_pre_order() {
        if (!m_head)
            return {};

        Node *tmp;
        std::stack<Node *> st;
        std::vector<int> items;

        st.push(m_head);
        while (!st.empty()) {
            tmp = st.top();
            st.pop();

            items.push_back(tmp->item);

            if (tmp->right)
                st.push(tmp->right);

            if (tmp->left)
                st.push(tmp->left);
        }

        return items;
    }

    std::vector<int> get_in_order() {
        if (!m_head)
            return {};

        std::vector<int> items;
        std::stack<Node *> st;
        Node *tmp = nullptr;

        st.push(m_head);
        while (!st.empty()) {
            tmp = st.top();

            if (tmp->left) {
                st.push(tmp->left);
            } else {
                while (!st.empty()) {
                    tmp = st.top();
                    st.pop();

                    items.push_back(tmp->item);
                    if (tmp->right) {
                        st.push(tmp->right);

                        if (tmp->right->left) {
                            break;
                        }
                    }
                }
            }
        }

        return items;
    }

    std::vector<int> get_post_order() {
        if (!m_head)
            return {};

        std::vector<int> items;
        std::stack<Node *> st;
        Node *tmp = nullptr;

        st.push(m_head);
        while (!st.empty()) {
            tmp = st.top();

            if (tmp->left) {
                st.push(tmp->left);
            } else {
                while (!st.empty()) {
                    tmp = st.top();
                    st.pop();

                    if (tmp->right) {

                        if (tmp->right->left)
                            items.push_back(tmp->right->left->item);

                        items.push_back(tmp->right->item);

                        if (tmp->right->right)
                            items.push_back(tmp->right->right->item);
                    }

                    items.push_back(tmp->item);
                }
            }
        }

        return items;
    }

    std::vector<int> get_level_order() {
        if (!m_head)
            return {};

        Node *tmp;
        std::queue<Node *> st;
        std::vector<int> items = {};

        st.push(m_head);

        while (!st.empty()) {
            tmp = st.front();
            st.pop();

            items.push_back(tmp->item);

            if (tmp->left) {
                st.push(tmp->left);
            }

            if (tmp->right) {
                st.push(tmp->right);
            }
        }

        return items;
    }
};

int main() {
    BinaryTree binaryTree;

    std::vector<int> items = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10/*, 11, 12, 13, 14, 15*/};

    for (int i: items)
        binaryTree.insert(i);

    std::cout << "Pre order traverse" << std::endl;
    print(binaryTree.get_pre_order());

    std::cout << "In order traverse" << std::endl;
    print(binaryTree.get_in_order());

    std::cout << "Post order traverse" << std::endl;
    print(binaryTree.get_post_order());

    std::cout << "Level order traverse" << std::endl;
    print(binaryTree.get_level_order());

    if (binaryTree.search(10))
        std::cout << "Node is find\n";
    else
        std::cout << "Node not find\n";

    std::cout << "Height of the three: " << binaryTree.get_height() << std::endl;
    std::cout << "Level of 5: " << binaryTree.get_level(5) << std::endl;

    if (binaryTree.is_complete()) {
        std::cout << "The Tree is Completed\n";
    } else {
        std::cout << "The Tree is not Completed\n";
    }

    if (binaryTree.is_almost_complete()) {
        std::cout << "The Tree is almost Completed\n";
    } else {
        std::cout << "The Tree is not almost Completed\n";
    }

    return 0;
}

tree.cc

/**
 * Tree:
 * - A tree is a hierarchical data structure consisting of nodes connected by edges.
 * - It consists of a root node, which is the topmost node, and zero or more child nodes.
 * - Each node can have an arbitrary number of children, unlike a binary tree which restricts each node to have at most two children.
 * - Trees are used to represent hierarchical relationships such as organizational charts, file systems, and HTML DOM structures.
 */

#include "iostream"
#include "vector"
#include "queue"
#include "stack"

struct Node {
    int item;
    Node *child1;
    Node *child2;
    Node *child3;
    Node *child4;

    explicit Node(int item, Node *child1 = nullptr, Node *child2 = nullptr, Node *child3 = nullptr, Node *child4 = nullptr) :
            item(item), child1(child1), child2(child2), child3(child3), child4(child4) {};
};

class Tree {
private:
    struct Node *m_head = nullptr;
public:
    Tree() : m_head(nullptr) {}

    ~Tree() {
        if (!m_head)
            return;

        std::stack<Node *> queue;
        queue.push(m_head);
        Node *current;

        while (!queue.empty()) {
            current = queue.top();
            queue.pop();

            if (current->child1)
                queue.push(current->child1);
            if (current->child2)
                queue.push(current->child2);
            if (current->child3)
                queue.push(current->child3);
            if (current->child4)
                queue.push(current->child4);

            delete current;
        }
    }

    void insert(int item) {
        Node *new_node = new Node(item);

        if (!m_head) {
            m_head = new_node;
            return;
        }

        std::queue<Node *> queue;
        queue.push(m_head);

        while (!queue.empty()) {
            Node *current = queue.front();
            queue.pop();

            if (!current->child1) {
                current->child1 = new_node;
                return;
            } else if (!current->child2) {
                current->child2 = new_node;
                return;
            } else if (!current->child3) {
                current->child3 = new_node;
                return;
            } else if (!current->child4) {
                current->child4 = new_node;
                return;
            }

            if (current->child1)
                queue.push(current->child1);

            if (current->child2)
                queue.push(current->child2);

            if (current->child3)
                queue.push(current->child3);

            if (current->child4)
                queue.push(current->child4);
        }
    }

    void print() {
        if (!m_head)
            return;

        m_print(m_head);
    }

    bool search(int find) {
        if (!m_head)
            return false;

        if (m_head->item == find)
            return true;

        return m_search(find, m_head);
    }

    void delete_node(int find) {
        if (!m_head)
            return;

        // Use level-order traversal to find the node to delete
        std::queue<Node *> queue;
        queue.push(m_head);
        Node *current = nullptr;
        Node *to_delete = nullptr;

        while (!queue.empty()) {
            current = queue.front();
            queue.pop();

            if (current->item == find) {
                to_delete = current;
                break;
            }

            if (current->child1)
                queue.push(current->child1);
            if (current->child2)
                queue.push(current->child2);
            if (current->child3)
                queue.push(current->child3);
            if (current->child4)
                queue.push(current->child4);
        }

        if (!to_delete) {
            std::cout << "Node with value " << find << " not found in the tree." << std::endl;
            return;
        }

        // Find the deepest node
        queue.push(m_head);
        Node *deepest_node = nullptr;
        while (!queue.empty()) {
            current = queue.front();
            queue.pop();

            if (current != to_delete) {
                deepest_node = current;
            }

            if (current->child1)
                queue.push(current->child1);
            if (current->child2)
                queue.push(current->child2);
            if (current->child3)
                queue.push(current->child3);
            if (current->child4)
                queue.push(current->child4);
        }

        // Swap values between to_delete and deepest_node
        if (deepest_node) {
            to_delete->item = deepest_node->item;

            // Delete deepest_node
            queue.push(m_head);
            while (!queue.empty()) {
                current = queue.front();
                queue.pop();

                if (current->child1 == deepest_node) {
                    delete current->child1;
                    current->child1 = nullptr;
                    break;
                } else if (current->child2 == deepest_node) {
                    delete current->child2;
                    current->child2 = nullptr;
                    break;
                } else if (current->child3 == deepest_node) {
                    delete current->child3;
                    current->child3 = nullptr;
                    break;
                } else if (current->child4 == deepest_node) {
                    delete current->child4;
                    current->child4 = nullptr;
                    break;
                }

                if (current->child1)
                    queue.push(current->child1);
                if (current->child2)
                    queue.push(current->child2);
                if (current->child3)
                    queue.push(current->child3);
                if (current->child4)
                    queue.push(current->child4);
            }
        } else {
            // If deepest_node is nullptr, it means to_delete is the root and the only node
            delete m_head;
            m_head = nullptr;
        }
    }

private:
    void m_print(Node *node) {
        if (!node)
            return;

        std::cout << node->item << ' ';

        m_print(node->child1);
        m_print(node->child2);
        m_print(node->child3);
        m_print(node->child4);
    }

    bool m_search(int find, Node *node) {
        if (!node)
            return false;

        if (find == node->item)
            return true;

        return m_search(find, node->child1) ||
               m_search(find, node->child2) ||
               m_search(find, node->child3) ||
               m_search(find, node->child4);
    }
};

int main() {
    Tree tree;
    std::vector<int> data/* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}*/;

    for (int i = 1; i < 100; i++)
        data.push_back(i);

    for (const int d: data)
        tree.insert(d);

    if (tree.search(30))
        std::cout << "Search: find";
    else
        std::cout << "Search: not-find";

    tree.delete_node(99);

    std::cout << std::endl;
    tree.print();
    std::cout << std::endl;

    return 0;
}

A tree data structure is a widely used abstract data type that simulates a hierarchical tree structure with a set of connected nodes. It is a non-linear data structure, as opposed to arrays, linked lists, stacks, and queues which are linear. Trees are used to represent data that has a hierarchical relationship between its elements.

Key Components of a Tree

• Node: The basic unit of a tree which contains data and links to other nodes.
• Root: The topmost node of a tree, which has no parent.
• Edge: The link between two nodes.
• Child: A node directly connected to another node when moving away from the root.
• Parent: The converse notion of a child.
• Leaf (External node): A node that does not have any children.
• Internal Node: A node that has at least one child.
• Subtree: A tree consisting of a node and its descendants.
• Depth of a node: The length of the path from the root to the node.
• Height of a node: The length of the longest path from the node to a leaf.
• Level: The set of all nodes at a particular depth.

Characteristics

• Hierarchical Structure: Trees naturally represent hierarchical data, like file systems or organizational charts.
• Recursive Nature: Each child of a node is itself a tree, allowing recursive algorithms to process trees efficiently.
• Uniqueness: Each child node has exactly one parent node (except for the root node).

Types of Trees

1. Binary Tree

   • Each node has at most two children, referred to as the left child and the right child.
   • Binary Search Tree (BST): A binary tree where the left subtree contains nodes with values less than the parent node, and the right subtree contains nodes with values greater than the parent node.
   • Balanced Trees: Trees like AVL and Red-Black trees that maintain height balance to ensure operations can be performed in O(log n) time.

2. Heap

   • A specialized tree-based structure that satisfies the heap property; in a max-heap, parent nodes have values greater than or equal to their children, while in a min-heap, parent nodes have values less than or equal to their children.

3. Trie (Prefix Tree)

   • Used to store a dynamic set or associative array where the keys are usually strings. It is efficient for retrieval operations, especially with a large set of strings.

4. B-Tree and B+ Tree

   • Self-balancing tree data structures that maintain sorted data and allow searches, sequential access, insertions, and deletions in logarithmic time. Commonly used in databases and filesystems.

5. N-ary Tree

   • A tree in which nodes can have more than two children.

Tree Traversal Methods

Traversal refers to the process of visiting each node in the tree exactly once in a systematic way.

• Pre-order Traversal: Visit the root node, then recursively traverse the left subtree, followed by the right subtree.
• In-order Traversal: Recursively traverse the left subtree, visit the root node, and then recursively traverse the right subtree. In a binary search tree, this results in nodes being visited in ascending order.
• Post-order Traversal: Recursively traverse the left subtree, then the right subtree, and visit the root node last.
• Level-order Traversal: Visit nodes level by level starting from the root, commonly implemented using a queue.

Common Operations

• Insertion: Adding a new node to the tree while maintaining its properties.
• Deletion: Removing a node from the tree and re-linking its children to maintain the tree structure.
• Searching: Finding a node with a given value.
• Traversal: Accessing each node in the tree systematically.

Applications of Trees

• Hierarchical Data Representation: File systems, organizational structures, and taxonomies.
• Searching Algorithms: Efficient data retrieval using structures like binary search trees.
• Sorting Algorithms: Trees can be used to implement efficient sorting algorithms like heapsort.
• Routing Algorithms: Used in networking for efficient routing and broadcasting.
• Expression Evaluation: Abstract syntax trees in compilers represent expressions and operations.
• Artificial Intelligence: Decision trees are used for making decisions based on conditions.

Advantages

• Dynamic Data Structure: Trees can grow and shrink during execution.
• Efficient Operations: Provide faster search and insertion operations compared to some other data structures.
• Reflect Hierarchical Relationships: Naturally model hierarchical data, making them suitable for representing structured information.

Example: Binary Search Tree (BST)

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

• Properties:
  • Left child < Parent node
  • Right child > Parent node
• Operations:
  • Search for 7:
    • Start at root (8). Since 7 < 8, go to left child (3).
    • Since 7 > 3, go to right child (6).
    • Since 7 > 6, go to right child (7). Found!

Conclusion

The tree data structure is fundamental in computer science due to its versatility and efficiency in representing and manipulating hierarchical data. Understanding trees is crucial for algorithm design, optimization, and solving complex computational problems.

---

Feel free to ask if you have questions about specific types of trees or their applications!

Definition of a Tree Data Structure:

A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges. It simulates a natural tree structure with a root node and subtrees of children, represented as a set of linked nodes. In this structure:

• Root Node: The topmost node without a parent.
• Edges: Connections between nodes.
• Parent and Child Nodes: Every node (except the root) has one parent and can have multiple children.
• Leaf Nodes: Nodes with no children.
• Acyclic: Trees do not contain cycles; there is only one unique path between any two nodes.

Key Properties:

• Connectedness: All nodes are reachable from the root node.
• Hierarchy: Represents data with a parent-child relationship.
• No Cycles: Ensures a clear, single pathway between nodes.

---

Types of Trees:

1. Binary Tree:

   • Definition: A tree where each node has at most two children, referred to as the left child and the right child.
   • Use Cases: Expression parsing, hierarchical data storage.

2. Binary Search Tree (BST):

   • Definition: A binary tree where the left subtree contains nodes with keys less than the parent node, and the right subtree contains nodes with keys greater than the parent node.
   • Use Cases: Efficient searching, insertion, and deletion operations (O(log n) time complexity in balanced BSTs).

3. Balanced Trees:

   • AVL Tree: Self-balancing BST where the heights of two child subtrees of any node differ by at most one.
   • Red-Black Tree: A BST with an extra bit of storage per node (color) to ensure the tree remains approximately balanced.
   • Use Cases: Situations requiring guaranteed O(log n) performance for insertions and deletions.

4. Heap:

   • Definition: A specialized tree-based structure satisfying the heap property (in a max-heap, parent nodes are greater than or equal to their children; in a min-heap, they are less than or equal).
   • Use Cases: Implementing priority queues, efficient retrieval of the maximum or minimum element.

5. Trie (Prefix Tree):

   • Definition: An n-ary tree used to store associative data structures where the keys are usually strings.
   • Use Cases: Autocomplete features, spell checking, IP routing.

6. B-Tree and B+ Tree:

   • Definition: Self-balancing search trees that maintain sorted data and allow searches, sequential access, insertions, and deletions in logarithmic time.
   • Use Cases: Databases and filesystems to manage large blocks of data.

7. N-ary Tree:

   • Definition: A tree in which nodes can have zero or more children (more than two).
   • Use Cases: Representing hierarchies like organizational structures, file systems.

8. Segment Tree:

   • Definition: A tree used for storing information about intervals or segments, allowing for efficient query and update operations.
   • Use Cases: Range queries and updates in arrays (e.g., sum, minimum).

9. Suffix Tree:

   • Definition: A compressed trie containing all the suffixes of the given text.
   • Use Cases: Fast pattern matching in strings, bioinformatics.

10. Spanning Tree:

    • Definition: A subset of a graph that covers all the vertices with the minimum possible number of edges.
    • Use Cases: Network design, circuit design.

11. Decision Tree:

    • Definition: A flowchart-like structure used for decision-making and machine learning, where each internal node represents a test on an attribute.
    • Use Cases: Classification, regression tasks in machine learning.

---

Summary:

• Trees are fundamental data structures that represent hierarchical relationships.
• Different types of trees are optimized for various operations and use cases.
• Understanding the specific characteristics and applications of each tree type helps in choosing the right one for a given problem.

---

Feel free to ask if you need more details on any specific type of tree or its implementation!

Certainly! Understanding the fundamental concepts of tree data structures is crucial for grasping how hierarchical data is organized and manipulated. Below, I'll explain each of the concepts you've mentioned—path, branch, height, depth, generation, level, degree, and more—in detail.

---

1. Path

Definition:
A path in a tree is a sequence of nodes connected by edges, starting from one node and moving to another node by traversing parent-child relationships.

Explanation:

• Simple Path: A path where all nodes (except possibly the first and last) are distinct.
• Length of a Path: The number of edges in the path (number of nodes minus one).

Example:
In the following tree:

      A
     / \
    B   C
       / \
      D   E

• The path from A to D is A → C → D.
• The length of this path is 2.

---

2. Branch

Definition:
A branch refers to a subtree originating from a node, including that node and all its descendants.

Explanation:

• Branching Factor: The number of children a node has; also referred to as the node's degree.
• In a physical tree analogy, branches split off from the main trunk; similarly, in data structures, branches represent subdivisions of the tree.

Example:

• The subtree starting at node C (including nodes C, D, and E) can be considered a branch of the tree rooted at A.

---

3. Height

Definition:
The height of a node is the length of the longest path from that node down to a leaf node. The height of the tree is the height of the root node.

Explanation:

• Leaf Nodes: Nodes with no children have a height of 0.
• Height Calculation: Height of a node = 1 + maximum height of its child nodes.

Example:
Using the previous tree:

• Node D and E are leaf nodes with a height of 0.
• Node C has a height of 1 (since its longest path to a leaf node is through either D or E).
• The root node A has a height of 2.

---

4. Depth

Definition:
The depth of a node is the length of the path from the root node to that node.

Explanation:

• Root Node: Has a depth of 0.
• Depth Calculation: Depth of a node = 1 + depth of its parent node.

Example:
Using the same tree:

• Node A (root) has a depth of 0.
• Node C has a depth of 1.
• Node D has a depth of 2.

---

5. Generation

Definition:
All nodes that are at the same depth or level in a tree can be considered to be in the same generation.

Explanation:

• Family Tree Analogy: Just like family generations, nodes at the same level are peers.
• Useful in algorithms that process nodes level by level.

Example:

• Nodes B and C are in the same generation (depth 1).
• Nodes D and E are in the same generation (depth 2).

---

6. Level

Definition:
The level of a node corresponds to its depth in the tree. Levels are often numbered starting from 0 at the root node.

Explanation:

• Level Numbering: Level number increases as you move down the tree.
• Purpose: Helps in organizing and visualizing the tree structure.

Example:

• Level 0: Node A
• Level 1: Nodes B, C
• Level 2: Nodes D, E

---

7. Degree

Definition:
The degree of a node is the number of children it has. The degree of a tree is the maximum degree of all its nodes.

Explanation:

• Leaf Nodes: Have a degree of 0.
• Internal Nodes: Nodes with at least one child.

Example:

• Node A has a degree of 2 (children B and C).
• Node C has a degree of 2 (children D and E).
• The tree's degree is 2 (since the maximum degree among all nodes is 2).

---

8. Ancestors and Descendants

Ancestors:

• Definition: All the nodes along the path from a given node up to the root node.
• Explanation: A node's parent, grandparent, and so on.

Descendants:

• Definition: All the nodes that can be reached by following paths downward from a given node.
• Explanation: A node's children, grandchildren, etc.

Example:

• Ancestors of D: C and A
• Descendants of C: D and E

---

9. Siblings

Definition:
Nodes that share the same parent node.

Explanation:

• Sibling Relationship: Nodes at the same level connected to the same parent.

Example:

• Nodes D and E are siblings (both children of C).
• Nodes B and C are siblings (both children of A).

---

10. Leaf Node (External Node)

Definition:
A node with no children.

Explanation:

• Endpoint Nodes: They do not lead to any other nodes.
• Role in Trees: Leaf nodes often represent the actual data or values in a tree structure.

Example:

• Nodes B, D, and E are leaf nodes.

---

11. Internal Node

Definition:
A node that has at least one child; not a leaf node.

Explanation:

• Intermediate Nodes: They connect leaf nodes to the root.
• Contribute to Tree Structure: Internal nodes determine the shape and balance of the tree.

Example:

• Nodes A and C are internal nodes.

---

12. Subtree

Definition:
A portion of a tree that consists of a node and all its descendants.

Explanation:

• Recursive Nature: Each child node can be considered the root of its own subtree.
• Use in Algorithms: Subtrees allow recursive operations on trees.

Example:

• The subtree rooted at C includes nodes C, D, and E.

---

13. Edge

Definition:
A connection between two nodes in a tree.

Explanation:

• Parent-Child Relationship: Edges define how nodes are related.
• Edge Count: In a tree with n nodes, there are n - 1 edges.

Example:

• Edge between A and B.
• Edge between C and D.

---

14. Forest

Definition:
A collection of disjoint trees (i.e., a set of trees that are not connected).

Explanation:

• Formation: Removing the root node from a tree results in a forest of its subtrees.
• Usage: Forests are used in graph theory and algorithms involving multiple trees.

Example:

• If you remove node A from the tree, you get a forest consisting of the subtrees rooted at B and C.

---

15. Ordered Tree

Definition:
A tree where the children of each node are ordered; that is, there is a defined sequence for the children.

Explanation:

• Significance of Order: In ordered trees, the position of a child node among its siblings matters.
• Applications: Syntax trees in compilers, XML parsing.

Example:

• In an expression tree, the order of operands affects the computation (e.g., in (A + B) * C).

---

16. Complete Binary Tree

Definition:
A binary tree in which all levels are fully filled except possibly the last level, which is filled from left to right.

Explanation:

• Properties: Efficient use of space.
• Applications: Used in heaps to implement priority queues.

Example:

        1
      /   \
     2     3
    / \   /
   4   5 6

• The tree is complete because all levels except the last are fully filled, and the last level is filled from left to right.

---

17. Full Binary Tree

Definition:
A binary tree in which every node has either 0 or 2 children.

Explanation:

• Leaf Nodes: All leaf nodes are at the same depth.
• Applications: Used in decision trees, where each decision leads to two possible outcomes.

Example:

        A
       / \
      B   C
     / \ / \
    D  E F  G

• Every node has 0 or 2 children.

---

18. Balanced Tree

Definition:
A tree where the heights of the two child subtrees of any node differ by no more than one.

Explanation:

• Purpose: To ensure operations like search, insert, and delete have optimal time complexity (O(log n)).
• Types of Balanced Trees: AVL trees, Red-Black trees.

Example:

• In an AVL tree, rotations are performed during insertions and deletions to maintain balance.

---

19. Degree of Tree

Definition:
The maximum degree of any node in the tree.

Explanation:

• Indicates Tree Type: For example, a tree with a degree of 2 is a binary tree.

Example:

• If the highest number of children any node has is 3, the tree's degree is 3.

---

20. Traversal Methods

Brief Overview:

• Pre-order Traversal: Visit the root node, traverse the left subtree, then the right subtree.
• In-order Traversal: Traverse the left subtree, visit the root node, then the right subtree (used in binary search trees to retrieve sorted data).
• Post-order Traversal: Traverse the left subtree, the right subtree, and then visit the root node.
• Level-order Traversal: Visit nodes level by level starting from the root (uses a queue data structure).

Example:
Given the tree:

      F
     / \
    B   G
   / \   \
  A   D   I
     / \  /
    C   E H

• In-order Traversal: A, B, C, D, E, F, G, H, I
• Pre-order Traversal: F, B, A, D, C, E, G, I, H
• Post-order Traversal: A, C, E, D, B, H, I, G, F

---

Additional Concepts

Parent Node

• Definition: The node that has an edge to a given node (its immediate predecessor).
• Example: Node A is the parent of nodes B and C.

Child Node

• Definition: A node that is a descendant of another node (its immediate successor).
• Example: Nodes B and C are children of node A.

Rooted Tree

• Definition: A tree in which one node is designated as the root, and every edge is directed away from the root.
• Explanation: Provides a reference point for measuring depth and defining parent-child relationships.

---

Practical Applications of These Concepts

• Algorithm Efficiency: Understanding depth and height helps in analyzing the time complexity of tree operations.
• Database Indexing: Trees are used in databases for indexing (e.g., B-trees), where balancing is crucial.
• File Systems: Directory structures are often represented as trees.
• Artificial Intelligence: Decision trees rely on the concepts of branches and leaf nodes to represent choices and outcomes.
• Networking: Routing protocols may use tree structures to determine paths.

---

Visual Representation

Understanding these concepts is often easier with visual aids. Here's a simple tree diagram labeling various concepts:

Level 0 (Depth 0, Generation 0)
       [Root]
         A
        / \
       /   \
Level 1 (Depth 1, Generation 1)
     [B]   [C]
     /     / \
Level 2 (Depth 2, Generation 2)
   [D]   [E] [F]

• Paths:
  • A to D: A → B → D
  • A to F: A → C → F
• Heights:
  • Height of D: 0
  • Height of B: 1 (since B leads to D)
  • Height of A: 2 (longest path to leaf D or F)
• Degrees:
  • Degree of A: 2
  • Degree of B: 1
  • Degree of C: 2
• Leaves (Leaf Nodes): D, E, F
• Internal Nodes: A, B, C

---

Conclusion

Understanding these fundamental concepts is essential for:

• Algorithm Design and Analysis: Optimizing search, insert, and delete operations.
• Data Organization: Efficiently storing and retrieving hierarchical data.
• Problem Solving: Applying appropriate tree structures to specific computational problems.

---

Feel free to ask for further clarification on any of these concepts or how they apply to specific types of trees or algorithms!

Here's a challenging problem that could be asked in senior-level interviews at companies like Facebook, Google, or Microsoft. It involves a mix of algorithmic thinking, data structures, and problem-solving skills expected of a senior software engineer.

Problem: "Find the Maximum Path Sum in a Binary Tree"

Given a binary tree, find the maximum path sum.

A path in the binary tree is defined as a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once, and the path must contain at least one node.

The path sum is the sum of the node values along the path.

Example:

Input:

      10
     /  \
    2   10
   / \    \
  20  1   -25
          /  \
         3    4

Output:

42

Explanation:

The maximum path sum is obtained by adding nodes 10 -> 2 -> 20, giving 42.

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• The value of each node is in the range [-10^4, 10^4].

Function Signature:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root: TreeNode) -> int:
    # Your code here

Key Points to Consider:

• The path can start and end at any node, which makes it different from problems that simply consider root-to-leaf paths.
• You may need to keep track of the maximum path sum found as you recurse, potentially using a helper function to facilitate calculations.
• Pay special attention to scenarios where negative values may be involved, and ensure the algorithm works correctly even with a mix of positive and negative numbers.

Take your time to implement this, and if you need any hints or suggestions, feel free to ask!