No history yet

Study Guide

📖 Core Concepts

Tree Fundamentals A tree is a non-linear data structure that organizes information hierarchically, starting from a single 'root' node and branching out, ideal for representing relationships.

C++ Node Structure In C++, a tree node is a struct or class containing a data value and self-referential pointers that hold the memory addresses of its children nodes.

Building a Tree Trees are built in C++ by dynamically allocating nodes on the heap with new and manually linking them by assigning child node addresses to parent pointers.

Tree Traversal (Pre-order) Traversal is the process of visiting every node in a tree; pre-order traversal follows a "visit-left-right" pattern, using recursion to navigate down each branch.

Searching a Tree A recursive function can search a tree by checking the current node's value and, if it's not a match, calling itself on the left and right subtrees.

Deleting a Tree To prevent memory leaks, dynamically allocated tree nodes must be destroyed using a post-order traversal to safely delete children before their parent.

📌 Must Remember

Tree Fundamentals

  1. Hierarchical vs. Linear: Unlike arrays or lists (linear), trees represent parent-child relationships, perfect for file systems or org charts.
  2. The Root: Every non-empty tree has exactly one root node, which is the single entry point to the structure.
  3. Nodes and Edges: Nodes hold data, and edges are the connections (pointers) between a parent and its children.
  4. Parent and Child: Any node with a connection leading to it is a child. The node it connects from is the parent.
  5. Leaf Nodes: Nodes with no children are called leaves; they are the endpoints of any path.
  6. Subtree: Any node and all its descendants form a subtree, which is itself a complete tree.

C++ Node Structure

  1. struct or class: A node is defined as a struct or class in C++.
  2. Data Member: The node structure must contain a variable to hold its own data (e.g., int data;).
  3. Self-Referential Pointers: The key feature is pointers of the same struct type (e.g., Node* left;), allowing it to point to other nodes.
  4. Binary Tree Constraint: A binary tree node has at most two children, typically named left and right.
  5. Blueprint: The node definition is just a blueprint; it doesn't create any nodes until you use new.

Building a Tree

  1. Dynamic Allocation: Nodes must be created on the heap using the new keyword (e.g., Node* root = new Node();).
  2. Heap Memory: Using new allocates memory that persists beyond the function's scope, which is necessary for a tree.
  3. Arrow Operator ->: To access members of a struct through a pointer, you must use the arrow operator (->), not the dot operator (.).
  4. nullptr: A pointer that doesn't point to anything should be initialized to nullptr to signify the absence of a node (e.g., a missing child).
  5. Manual Wiring: You connect nodes by assigning the memory address of one node to the pointer of another (e.g., root->left = child1;).

Tree Traversal (Pre-order)

  1. Traversal Goal: The purpose of traversal is to systematically visit every node in the tree exactly once.
  2. Recursion is Key: Tree traversal is naturally recursive; a function calls itself on a node's children.
  3. Base Case: The recursion must have a base case to stop: if (node == nullptr) return;. This prevents infinite loops and crashes.
  4. Pre-order Sequence: The order is always: 1) Process the current node, 2) Traverse the left subtree, 3) Traverse the right subtree.
  5. Call Stack: Each recursive call adds a new frame to the program's call stack, which keeps track of where to return.

Searching a Tree

  1. Boolean Return: A search function typically returns true if the value is found and false otherwise.
  2. Three Checks: In each recursive call, you check three things: 1) Is the current node null? (return false), 2) Is the current node the target? (return true), 3) If not, search left and right.
  3. Divide and Conquer: The search works by breaking the problem down: if the value isn't here, it might be in the left or right half (subtree).
  4. Recursive Search Call: The logic is return search(node->left, value) || search(node->right, value);.
  5. Graceful Failure: The search ends gracefully when it reaches a nullptr, which acts as the base case for a failed path.

Deleting a Tree

  1. Memory Leaks: Forgetting to delete memory allocated with new causes a memory leak, where your program loses memory it can no longer access.
  2. delete Keyword: The delete keyword frees up the memory that a pointer points to, making it available for other parts of the program.
  3. Post-order Deletion is Mandatory: You must delete a node's children before deleting the node itself. Otherwise, you lose the pointers to the children and can't delete them.
  4. Post-order Sequence: The order is: 1) Traverse and delete the left subtree, 2) Traverse and delete the right subtree, 3) Delete the current node.
  5. Dangling Pointers: After deleting a node, set the pointer that pointed to it to nullptr to avoid it becoming a 'dangling pointer'.

📚 Key Terms

Node A fundamental unit of a tree that contains a data value and pointers to its child nodes.

  • Used in context: We created a new Node on the heap and set its data field to 10.
  • Topic: Tree Fundamentals

Root The single, top-most node in a tree from which all other nodes descend; it has no parent.

  • Used in context: The search algorithm always begins at the root of the tree.
  • Topic: Tree Fundamentals

Edge The conceptual link between a parent node and a child node, represented in C++ by a pointer.

  • Used in context: An edge connects the root to its left child, showing their relationship.
  • Topic: Tree Fundamentals

Leaf Node A node that has no children; it is at the end of a branch.

  • Used in context: When our traversal hits a leaf node, its left and right pointers will both be nullptr.
  • Topic: Tree Fundamentals

Parent / Child A relationship where a parent node has pointers pointing to its child nodes.

  • Used in context: The root node is the parent of two other nodes, which are its child nodes.
  • Topic: Tree Fundamentals

Binary Tree A specific type of tree where each node can have at most two children, a 'left' child and a 'right' child.

  • Used in context: Our C++ Node struct is designed for a Binary Tree because it only has left and right pointers.
  • Topic: C++ Node Structure

new A C++ keyword used for dynamic memory allocation, which reserves memory on the heap for an object.

  • Used in context: We used new Node() to create a node that will persist after the function finishes.
  • Topic: Building a Tree

delete A C++ keyword used to deallocate memory that was previously allocated with new, preventing memory leaks.

  • Used in context: After traversing the entire left subtree, we call delete on the left child's parent.
  • Topic: Deleting a Tree

nullptr A C++ keyword representing a null pointer, used to indicate that a pointer does not point to any valid memory address.

  • Used in context: A leaf node's child pointers are set to nullptr to show it has no children.
  • Topic: Building a Tree

Pointer A variable that stores the memory address of another variable.

  • Used in context: The root pointer holds the memory address of the first node we created on the heap.
  • Topic: C++ Node Structure

Traversal The process of visiting each node in a tree data structure in a systematic order.

  • Used in context: We implemented a pre-order traversal function to print every value in the tree.
  • Topic: Tree Traversal (Pre-order)

Recursion A programming technique where a function calls itself in order to solve a problem by breaking it into smaller, self-similar subproblems.

  • Used in context: Tree traversal is elegantly solved with recursion, where the traversal function calls itself for the left and right children.
  • Topic: Tree Traversal (Pre-order)

Base Case The condition in a recursive function that stops the recursion and prevents an infinite loop.

  • Used in context: The base case for our traversal is if (node == nullptr), which stops the function from trying to access a non-existent node.
  • Topic: Tree Traversal (Pre-order)

Memory Leak A resource management error where a program allocates memory but loses the ability to free it, consuming resources unnecessarily.

  • Used in context: If we don't delete every node we create with new, our program will have a memory leak.
  • Topic: Deleting a Tree

Pre-order Traversal A traversal algorithm that follows the order: 1. Visit the current node, 2. Traverse the left subtree, 3. Traverse the right subtree.

  • Used in context: A Pre-order Traversal is useful for creating a copy of a tree.
  • Topic: Tree Traversal (Pre-order)

Post-order Traversal A traversal algorithm that follows the order: 1. Traverse the left subtree, 2. Traverse the right subtree, 3. Visit the current node.

  • Used in context: We must use Post-order Traversal to safely delete a tree, as it ensures children are deleted before their parent.
  • Topic: Deleting a Tree

🔍 Key Comparisons

Linear vs. Hierarchical Data Structures

FeatureLinear Structures (Array, List)Hierarchical Structures (Tree)
OrganizationSequential, one-after-the-other.Parent-child, top-down branching.
RelationshipsEach element has at most one before and one after.Each element (node) can have multiple children.
AccessOften sequential (e.g., iterating) or direct by index.Starts at the root and follows paths (edges).
Use CaseStoring a simple sequence of items.Representing file systems, org charts, DOM.

Memory trick: A List is like a Line. A Tree looks like a Tree.

Topic: Tree Fundamentals

Pre-order vs. Post-order Traversal

FeaturePre-order TraversalPost-order Traversal
OrderVisit -> Left -> RightLeft -> Right -> Visit
Parent ProcessingThe parent node is processed before its children.The parent node is processed after all its children.
Primary Use CaseCopying a tree, printing nodes in a top-down fashion.Safely deleting a tree, evaluating expression trees.
Example OutputRoot is printed first.Leaf nodes are printed first, root is last.

Memory trick: Pre-order processes the parent pre-emptively (first). Post-order processes the parent post-mortem (last).

Topic: Deleting a Tree

⚠️ Common Mistakes

❌ MISTAKE: Accessing a node's data with the dot operator (root.data).

  • Why it happens: This is the correct syntax for objects, but not for pointers to objects.
  • ✅ Instead: Use the arrow operator -> to access members via a pointer: root->data.
  • Memory aid: The arrow -> looks like it's 'pointing' to the member.
  • Topic: Building a Tree

❌ MISTAKE: Forgetting the base case in a recursive traversal function.

  • Why it happens: It's easy to focus on the recursive step and forget the condition that stops it.
  • ✅ Instead: Always start a recursive tree function with if (node == nullptr) { return; }. This handles empty trees and leaf nodes correctly.
  • Topic: Tree Traversal (Pre-order)

❌ MISTAKE: Deleting a parent node before its children.

  • Why it happens: A simple pre-order traversal might seem like a logical way to delete, but it orphans the children.
  • ✅ Instead: Always use a post-order traversal for deletion. This guarantees you delete from the leaves up to the root, never losing access to any node.
  • Topic: Deleting a Tree

❌ MISTAKE: Writing a search function that only checks the left or right side, not both.

  • Why it happens: The logic can be tricky. A common error is if (search(left)) return true; else return search(right);, which incorrectly returns false if the value is on the right side but not the left.
  • ✅ Instead: Use the logical OR operator to combine the results: return search(node->left, value) || search(node->right, value);.
  • Topic: Searching a Tree

❌ MISTAKE: Assuming a new node's pointers are automatically nullptr.

  • Why it happens: When you allocate memory with new, the contents are uninitialized and contain garbage values, not nullptr.
  • ✅ Instead: After creating a node, always explicitly initialize its pointers: newNode->left = nullptr; and newNode->right = nullptr;.
  • Topic: Building a Tree

🔄 Key Processes

Pre-order Traversal Process

Goal: Print the value of every node in a tree, starting from the root.

Step 1: Define the Base Case

  • What happens: Check if the current node pointer is nullptr. If it is, the function immediately returns, stopping this path of recursion.
  • Key indicator: if (node == nullptr) return;

Step 2: Process the Current Node

  • What happens: Perform the 'visit' action on the current node. This is often printing its value, but could be any operation.
  • Key indicator: cout << node->data << endl;

Step 3: Recurse on the Left Child

  • What happens: Call the same traversal function, passing the current node's left child pointer as the new argument.
  • Key indicator: traverse(node->left);

Step 4: Recurse on the Right Child

  • What happens: Call the same traversal function again, this time passing the current node's right child pointer.
  • Key indicator: traverse(node->right);

Topic: Tree Traversal (Pre-order)

Recursive Search Process

Goal: Determine if a specific value exists anywhere in the tree.

Step 1: Base Case - Not Found

  • What happens: Check if the current node is nullptr. If so, we've reached the end of a branch without finding the value. Return false.
  • Key indicator: if (node == nullptr) return false;

Step 2: Base Case - Found

  • What happens: Check if the current node's data matches the target value. If so, the search is successful. Return true.
  • Key indicator: if (node->data == targetValue) return true;

Step 3: Recurse and Combine Results

  • What happens: If the value hasn't been found yet, recursively call the search function on both the left and right children. Return true if either of these calls returns true.
  • Key indicator: return search(node->left, targetValue) || search(node->right, targetValue);

Topic: Searching a Tree

Post-order Deletion Process

Goal: Safely delete every node in the tree to prevent memory leaks.

Step 1: Define the Base Case

  • What happens: Check if the current node pointer is nullptr. If it is, there is nothing to delete, so the function returns.
  • Key indicator: if (node == nullptr) return;

Step 2: Recurse and Delete Left Subtree

  • What happens: Call the same deletion function on the current node's left child. This ensures the entire left subtree is deleted before proceeding.
  • Key indicator: deleteTree(node->left);

Step 3: Recurse and Delete Right Subtree

  • What happens: Call the same deletion function on the current node's right child.
  • Key indicator: deleteTree(node->right);

Step 4: Delete the Current Node

  • What happens: Now that both children (and all their descendants) have been deleted, it is safe to delete the current node.
  • Key indicator: delete node;

Topic: Deleting a Tree

📝 Worked Examples

#include <iostream>

// The blueprint for our tree nodes
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Function to print the tree using Pre-order traversal
void printTreePreOrder(Node* node) {
    // Base case: stop if the node is null
    if (node == nullptr) {
        return;
    }
    // 1. Visit the current node
    std::cout << node->data << " ";
    // 2. Traverse left subtree
    printTreePreOrder(node->left);
    // 3. Traverse right subtree
    printTreePreOrder(node->right);
}

// Function to delete the entire tree using Post-order traversal
void deleteTree(Node* node) {
    // Base case: stop if the node is null
    if (node == nullptr) {
        return;
    }
    // 1. Traverse and delete left subtree
    deleteTree(node->left);
    // 2. Traverse and delete right subtree
    deleteTree(node->right);
    // 3. Delete the current node
    std::cout << "Deleting node: " << node->data << std::endl;
    delete node;
}

int main() {
    // --- Part 1: Building the Tree ---
    // Create the root node on the heap
    Node* root = new Node();
    root->data = 10;
    root->left = nullptr;
    root->right = nullptr;

    // Create a left child
    Node* leftChild = new Node();
    leftChild->data = 5;
    leftChild->left = nullptr;
    leftChild->right = nullptr;

    // Create a right child
    Node* rightChild = new Node();
    rightChild->data = 15;
    rightChild->left = nullptr;
    rightChild->right = nullptr;

    // Manually link the children to the root
    root->left = leftChild;
    root->right = rightChild;

    // --- Part 2: Traversing the Tree ---
    std::cout << "Tree values (Pre-order): ";
    printTreePreOrder(root);
    std::cout << std::endl << std::endl;

    // --- Part 3: Deleting the Tree ---
    deleteTree(root);

    // Set the original pointer to null to avoid a dangling pointer
    root = nullptr;

    return 0;
}

/*
Expected Output:

Tree values (Pre-order): 10 5 15 

Deleting node: 5
Deleting node: 15
Deleting node: 10

*/