Trees

Trees are hierarchical data structures that represent parent-child relationships between elements. Like a family tree or file system directory structure, trees organize data in a branching pattern where each element (node) can have multiple children but only one parent, enabling efficient organization and traversal of hierarchical information.

Interactive Visualization

Binary Search Tree Operations

Insert Node

Add new node maintaining BST property

Search Node

Find node with binary search

Delete Node

Remove node while preserving BST

Binary Search Tree Visualization

Tree Height: 4

Total Nodes: 7

How BST Operations Work:

Insert (O(log n)):

Compare with current node. Go left if smaller, right if larger. Insert when you reach a null pointer.

Search (O(log n)):

Follow the same path as insert. If you find the value, return true. If you reach null, return false.

Delete (O(log n)):

Three cases: no children (simple removal), one child (replace with child), two children (replace with successor).

BST Property:

For every node: all values in the left subtree are smaller, and all values in the right subtree are larger. This property enables efficient O(log n) operations by eliminating half the search space at each step.

Key Terminology

Node

A single element in the tree containing data and references to its children. The basic building block of any tree structure.

Root

The topmost node in the tree with no parent. Every tree has exactly one root node that serves as the entry point.

Parent & Child

Parent nodes have one or more children. Each child has exactly one parent, creating the hierarchical relationship.

Leaf

A node with no children. Leaf nodes are the endpoints of the tree structure, containing no further branches.

Edge

The connection between a parent and child node. A tree with n nodes has exactly n-1 edges.

Subtree

A tree formed by a node and all its descendants. Any node in a tree can be considered the root of its subtree.

Height

The longest path from the root to any leaf node. A tree with only a root has height 0.

Depth

The distance from the root to a specific node. The root has depth 0, its children have depth 1, and so on.

Level

All nodes at the same depth form a level. Level 0 contains only the root, level 1 contains its children, etc.

Types of Trees

Trees come in many varieties, each optimized for specific use cases and operations. Here are the most common types:

Binary Trees

Each node has at most two children, typically called left and right. Simple structure enables efficient algorithms.

Use cases: Expression trees, decision trees, heap implementation

Binary Search Trees (BST)

Binary trees with ordering property: left subtree < node < right subtree. Enables efficient searching and sorting.

Use cases: Databases, symbol tables, sorted collections

AVL Trees

Self-balancing BSTs where the height difference between left and right subtrees is at most 1. Guarantees O(log n) operations.

Use cases: Applications requiring guaranteed performance

Red-Black Trees

Self-balancing BSTs using color coding to maintain balance. Less strictly balanced than AVL but faster insertions/deletions.

Use cases: Standard library implementations (map, set)

Heaps

Complete binary trees where parent nodes are either greater (max-heap) or smaller (min-heap) than their children.

Use cases: Priority queues, heap sort algorithm

Tries (Prefix Trees)

Trees where each node represents a character, and paths from root to leaves represent strings or words.

Use cases: Autocomplete, spell checkers, IP routing

Focus: Binary Search Trees

Among all tree types, Binary Search Trees represent one of the most fundamental and widely-used implementations. A BST is a binary tree with a special ordering property that makes it incredibly efficient for search operations. Let's explore this powerful data structure in detail.

The BST Property

For every node in a Binary Search Tree: all values in the left subtree are smaller than the node's value, and all values in the right subtree are larger. This recursive property enables binary search with O(log n) efficiency, making BSTs ideal for dynamic datasets requiring frequent search operations.

BST Core Property

The BST Invariant

For every node in a Binary Search Tree:

• Left Subtree: All values are strictly less than the node's value
• Right Subtree: All values are strictly greater than the node's value
• Recursive Property: This rule applies to every subtree in the BST
• No Duplicates: Each value appears at most once in the tree

Why This Property Matters

This ordering property enables powerful optimizations:

• Binary Search: At each node, eliminate half the remaining search space
• Sorted Traversal: Inorder traversal yields elements in sorted order
• Range Queries: Efficiently find all values in a given range
• Predecessor/Successor: Quick access to next smaller/larger elements

Advantages & Disadvantages

✅ Advantages

• Fast Operations: Search, insert, and delete in O(log n) average time
• Sorted Order: Inorder traversal gives elements in sorted sequence
• Dynamic Size: Grows and shrinks efficiently during runtime
• No Extra Memory: No need to pre-allocate space like arrays
• Range Queries: Efficiently find elements within a range
• Flexible Operations: Supports min/max, predecessor/successor queries

⚠️ Disadvantages

• Balance Risk: Can become unbalanced, degrading to O(n) operations
• Worst Case: Sequential insertions create a linked list structure
• Memory Overhead: Extra memory needed for storing left/right pointers
• Cache Performance: Poor locality of reference compared to arrays
• No Random Access: Cannot access elements by index in O(1) time
• Complex Implementation: More complex than simple data structures

Complexity Analysis

Operation	Average Case	Worst Case	Description
Search	O(log n)	O(n)	Binary search through the tree structure
Insertion	O(log n)	O(n)	Find position and insert new node
Deletion	O(log n)	O(n)	Find node and restructure tree if needed
Traversal	O(n)	O(n)	Visit all nodes (inorder gives sorted sequence)
Space	O(n)	O(n)	Linear space for n nodes plus recursion stack

Balance is Key: Average case assumes a reasonably balanced tree. In worst case (skewed tree), operations degrade to O(n). Self-balancing variants like AVL or Red-Black trees guarantee O(log n) operations.

Code Examples: BST Implementation

Complete Binary Search Tree implementation with insert, search, and traversal methods. These examples demonstrate the BST property in practice and include utility methods for validation and analysis.

 class TreeNode:
    """
    A node in a Binary Search Tree
    Contains data and references to left and right children
    """
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    """
    Binary Search Tree implementation with core BST property:
    - All values in left subtree < node value
    - All values in right subtree > node value
    - This property enables efficient O(log n) operations
    """
    
    def __init__(self):
        """Initialize an empty BST"""
        self.root = None
        self.size = 0
    
    def insert(self, value):
        """
        Insert a value into the BST while maintaining BST property
        
        Time Complexity: O(log n) average, O(n) worst case
        Space Complexity: O(log n) average (recursion stack)
        """
        if self.root is None:
            self.root = TreeNode(value)
            self.size += 1
            print(f"Inserted {value} as root")
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        """Helper method for recursive insertion"""
        if value < node.value:
            # Insert in left subtree
            if node.left is None:
                node.left = TreeNode(value)
                self.size += 1
                print(f"Inserted {value} to the left of {node.value}")
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            # Insert in right subtree
            if node.right is None:
                node.right = TreeNode(value)
                self.size += 1
                print(f"Inserted {value} to the right of {node.value}")
            else:
                self._insert_recursive(node.right, value)
        else:
            print(f"Value {value} already exists in the tree")
    
    def search(self, value):
        """
        Search for a value in the BST
        
        Time Complexity: O(log n) average, O(n) worst case
        Space Complexity: O(log n) average (recursion stack)
        
        Returns: TreeNode if found, None otherwise
        """
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        """Helper method for recursive search"""
        if node is None:
            print(f"Value {value} not found in tree")
            return None
        
        if value == node.value:
            print(f"Found {value} in the tree")
            return node
        elif value < node.value:
            print(f"Searching left subtree from {node.value}")
            return self._search_recursive(node.left, value)
        else:
            print(f"Searching right subtree from {node.value}")
            return self._search_recursive(node.right, value)
    
    def find_min(self, node=None):
        """Find the minimum value in the tree (leftmost node)"""
        if node is None:
            node = self.root
        
        if node is None:
            return None
        
        while node.left is not None:
            node = node.left
        return node.value
    
    def find_max(self, node=None):
        """Find the maximum value in the tree (rightmost node)"""
        if node is None:
            node = self.root
        
        if node is None:
            return None
        
        while node.right is not None:
            node = node.right
        return node.value
    
    def inorder_traversal(self):
        """
        Perform inorder traversal (left, root, right)
        Returns values in sorted order for a BST
        """
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        """Helper method for inorder traversal"""
        if node is not None:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)
    
    def height(self):
        """Calculate the height of the tree"""
        return self._height_recursive(self.root)
    
    def _height_recursive(self, node):
        """Helper method to calculate height recursively"""
        if node is None:
            return -1
        
        left_height = self._height_recursive(node.left)
        right_height = self._height_recursive(node.right)
        return max(left_height, right_height) + 1
    
    def is_valid_bst(self):
        """Validate that the tree maintains BST property"""
        return self._validate_bst(self.root, float('-inf'), float('inf'))
    
    def _validate_bst(self, node, min_val, max_val):
        """Helper method to validate BST property"""
        if node is None:
            return True
        
        if node.value <= min_val or node.value >= max_val:
            return False
        
        return (self._validate_bst(node.left, min_val, node.value) and
                self._validate_bst(node.right, node.value, max_val))

# Example usage demonstrating BST operations
def demonstrate_bst():
    """Demonstrate BST operations with examples"""
    bst = BinarySearchTree()
    
    print("=== Binary Search Tree Demo ===")
    print("Inserting values: 50, 30, 70, 20, 40, 60, 80")
    
    # Insert values to create a balanced tree
    values = [50, 30, 70, 20, 40, 60, 80]
    for value in values:
        bst.insert(value)
    
    print(f"\nTree size: {bst.size}")
    print(f"Tree height: {bst.height()}")
    print(f"Is valid BST: {bst.is_valid_bst()}")
    
    # Search operations
    print("\n=== Search Operations ===")
    search_values = [40, 25, 70, 100]
    for value in search_values:
        result = bst.search(value)
        status = "Found" if result else "Not found"
        print(f"Search {value}: {status}")
    
    # Tree traversal
    print("\n=== Tree Traversal ===")
    inorder = bst.inorder_traversal()
    print(f"Inorder traversal (sorted): {inorder}")
    
    # Min/Max values
    print(f"\nMinimum value: {bst.find_min()}")
    print(f"Maximum value: {bst.find_max()}")

if __name__ == "__main__":
    demonstrate_bst() 
 /**
 * TreeNode class representing a node in the Binary Search Tree
 */
class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

/**
 * Binary Search Tree implementation with core BST property:
 * - All values in left subtree < node value
 * - All values in right subtree > node value
 * - This property enables efficient O(log n) operations
 */
public class BinarySearchTree {
    private TreeNode root;
    private int size;
    
    /**
     * Initialize an empty BST
     */
    public BinarySearchTree() {
        this.root = null;
        this.size = 0;
    }
    
    /**
     * Insert a value into the BST while maintaining BST property
     * 
     * Time Complexity: O(log n) average, O(n) worst case
     * Space Complexity: O(log n) average (recursion stack)
     */
    public void insert(int value) {
        if (root == null) {
            root = new TreeNode(value);
            size++;
            System.out.println("Inserted " + value + " as root");
        } else {
            insertRecursive(root, value);
        }
    }
    
    /**
     * Helper method for recursive insertion
     */
    private void insertRecursive(TreeNode node, int value) {
        if (value < node.value) {
            // Insert in left subtree
            if (node.left == null) {
                node.left = new TreeNode(value);
                size++;
                System.out.println("Inserted " + value + " to the left of " + node.value);
            } else {
                insertRecursive(node.left, value);
            }
        } else if (value > node.value) {
            // Insert in right subtree
            if (node.right == null) {
                node.right = new TreeNode(value);
                size++;
                System.out.println("Inserted " + value + " to the right of " + node.value);
            } else {
                insertRecursive(node.right, value);
            }
        } else {
            System.out.println("Value " + value + " already exists in the tree");
        }
    }
    
    /**
     * Search for a value in the BST
     * 
     * Time Complexity: O(log n) average, O(n) worst case
     * Space Complexity: O(log n) average (recursion stack)
     * 
     * @return TreeNode if found, null otherwise
     */
    public TreeNode search(int value) {
        return searchRecursive(root, value);
    }
    
    /**
     * Helper method for recursive search
     */
    private TreeNode searchRecursive(TreeNode node, int value) {
        if (node == null) {
            System.out.println("Value " + value + " not found in tree");
            return null;
        }
        
        if (value == node.value) {
            System.out.println("Found " + value + " in the tree");
            return node;
        } else if (value < node.value) {
            System.out.println("Searching left subtree from " + node.value);
            return searchRecursive(node.left, value);
        } else {
            System.out.println("Searching right subtree from " + node.value);
            return searchRecursive(node.right, value);
        }
    }
    
    /**
     * Find the minimum value in the tree (leftmost node)
     */
    public Integer findMin() {
        return findMin(root);
    }
    
    private Integer findMin(TreeNode node) {
        if (node == null) {
            return null;
        }
        
        while (node.left != null) {
            node = node.left;
        }
        return node.value;
    }
    
    /**
     * Find the maximum value in the tree (rightmost node)
     */
    public Integer findMax() {
        return findMax(root);
    }
    
    private Integer findMax(TreeNode node) {
        if (node == null) {
            return null;
        }
        
        while (node.right != null) {
            node = node.right;
        }
        return node.value;
    }
    
    /**
     * Perform inorder traversal (left, root, right)
     * Returns values in sorted order for a BST
     */
    public java.util.List<Integer> inorderTraversal() {
        java.util.List<Integer> result = new java.util.ArrayList<>();
        inorderRecursive(root, result);
        return result;
    }
    
    /**
     * Helper method for inorder traversal
     */
    private void inorderRecursive(TreeNode node, java.util.List<Integer> result) {
        if (node != null) {
            inorderRecursive(node.left, result);
            result.add(node.value);
            inorderRecursive(node.right, result);
        }
    }
    
    /**
     * Calculate the height of the tree
     */
    public int height() {
        return heightRecursive(root);
    }
    
    /**
     * Helper method to calculate height recursively
     */
    private int heightRecursive(TreeNode node) {
        if (node == null) {
            return -1;
        }
        
        int leftHeight = heightRecursive(node.left);
        int rightHeight = heightRecursive(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    /**
     * Validate that the tree maintains BST property
     */
    public boolean isValidBST() {
        return validateBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    /**
     * Helper method to validate BST property
     */
    private boolean validateBST(TreeNode node, int minVal, int maxVal) {
        if (node == null) {
            return true;
        }
        
        if (node.value <= minVal || node.value >= maxVal) {
            return false;
        }
        
        return validateBST(node.left, minVal, node.value) &&
               validateBST(node.right, node.value, maxVal);
    }
    
    /**
     * Get the size of the tree
     */
    public int size() {
        return size;
    }
    
    /**
     * Demonstrate BST operations with examples
     */
    public static void demonstrateBST() {
        System.out.println("=== Binary Search Tree Demo ===");
        BinarySearchTree bst = new BinarySearchTree();
        
        System.out.println("Inserting values: 50, 30, 70, 20, 40, 60, 80");
        
        // Insert values to create a balanced tree
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }
        
        System.out.println("\nTree size: " + bst.size());
        System.out.println("Tree height: " + bst.height());
        System.out.println("Is valid BST: " + bst.isValidBST());
        
        // Search operations
        System.out.println("\n=== Search Operations ===");
        int[] searchValues = {40, 25, 70, 100};
        for (int value : searchValues) {
            TreeNode result = bst.search(value);
            String status = (result != null) ? "Found" : "Not found";
            System.out.println("Search " + value + ": " + status);
        }
        
        // Tree traversal
        System.out.println("\n=== Tree Traversal ===");
        java.util.List<Integer> inorder = bst.inorderTraversal();
        System.out.println("Inorder traversal (sorted): " + inorder);
        
        // Min/Max values
        System.out.println("\nMinimum value: " + bst.findMin());
        System.out.println("Maximum value: " + bst.findMax());
    }
    
    public static void main(String[] args) {
        demonstrateBST();
    }
} 
 #include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

/**
 * TreeNode struct representing a node in the Binary Search Tree
 */
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

/**
 * Binary Search Tree implementation with core BST property:
 * - All values in left subtree < node value
 * - All values in right subtree > node value
 * - This property enables efficient O(log n) operations
 */
class BinarySearchTree {
private:
    TreeNode* root;
    int treeSize;
    
    /**
     * Helper method for recursive insertion
     */
    void insertRecursive(TreeNode* node, int value) {
        if (value < node->value) {
            // Insert in left subtree
            if (node->left == nullptr) {
                node->left = new TreeNode(value);
                treeSize++;
                cout << "Inserted " << value << " to the left of " << node->value << endl;
            } else {
                insertRecursive(node->left, value);
            }
        } else if (value > node->value) {
            // Insert in right subtree
            if (node->right == nullptr) {
                node->right = new TreeNode(value);
                treeSize++;
                cout << "Inserted " << value << " to the right of " << node->value << endl;
            } else {
                insertRecursive(node->right, value);
            }
        } else {
            cout << "Value " << value << " already exists in the tree" << endl;
        }
    }
    
    /**
     * Helper method for recursive search
     */
    TreeNode* searchRecursive(TreeNode* node, int value) {
        if (node == nullptr) {
            cout << "Value " << value << " not found in tree" << endl;
            return nullptr;
        }
        
        if (value == node->value) {
            cout << "Found " << value << " in the tree" << endl;
            return node;
        } else if (value < node->value) {
            cout << "Searching left subtree from " << node->value << endl;
            return searchRecursive(node->left, value);
        } else {
            cout << "Searching right subtree from " << node->value << endl;
            return searchRecursive(node->right, value);
        }
    }
    
    /**
     * Helper method for inorder traversal
     */
    void inorderRecursive(TreeNode* node, vector<int>& result) {
        if (node != nullptr) {
            inorderRecursive(node->left, result);
            result.push_back(node->value);
            inorderRecursive(node->right, result);
        }
    }
    
    /**
     * Helper method to calculate height recursively
     */
    int heightRecursive(TreeNode* node) {
        if (node == nullptr) {
            return -1;
        }
        
        int leftHeight = heightRecursive(node->left);
        int rightHeight = heightRecursive(node->right);
        return max(leftHeight, rightHeight) + 1;
    }
    
    /**
     * Helper method to validate BST property
     */
    bool validateBST(TreeNode* node, long minVal, long maxVal) {
        if (node == nullptr) {
            return true;
        }
        
        if (node->value <= minVal || node->value >= maxVal) {
            return false;
        }
        
        return validateBST(node->left, minVal, node->value) &&
               validateBST(node->right, node->value, maxVal);
    }
    
    /**
     * Helper method to cleanup memory
     */
    void destroyTree(TreeNode* node) {
        if (node != nullptr) {
            destroyTree(node->left);
            destroyTree(node->right);
            delete node;
        }
    }

public:
    /**
     * Initialize an empty BST
     */
    BinarySearchTree() : root(nullptr), treeSize(0) {}
    
    /**
     * Destructor to clean up allocated memory
     */
    ~BinarySearchTree() {
        destroyTree(root);
    }
    
    /**
     * Insert a value into the BST while maintaining BST property
     * 
     * Time Complexity: O(log n) average, O(n) worst case
     * Space Complexity: O(log n) average (recursion stack)
     */
    void insert(int value) {
        if (root == nullptr) {
            root = new TreeNode(value);
            treeSize++;
            cout << "Inserted " << value << " as root" << endl;
        } else {
            insertRecursive(root, value);
        }
    }
    
    /**
     * Search for a value in the BST
     * 
     * Time Complexity: O(log n) average, O(n) worst case
     * Space Complexity: O(log n) average (recursion stack)
     * 
     * @return TreeNode* if found, nullptr otherwise
     */
    TreeNode* search(int value) {
        return searchRecursive(root, value);
    }
    
    /**
     * Find the minimum value in the tree (leftmost node)
     */
    int findMin() {
        if (root == nullptr) {
            throw runtime_error("Tree is empty");
        }
        
        TreeNode* current = root;
        while (current->left != nullptr) {
            current = current->left;
        }
        return current->value;
    }
    
    /**
     * Find the maximum value in the tree (rightmost node)
     */
    int findMax() {
        if (root == nullptr) {
            throw runtime_error("Tree is empty");
        }
        
        TreeNode* current = root;
        while (current->right != nullptr) {
            current = current->right;
        }
        return current->value;
    }
    
    /**
     * Perform inorder traversal (left, root, right)
     * Returns values in sorted order for a BST
     */
    vector<int> inorderTraversal() {
        vector<int> result;
        inorderRecursive(root, result);
        return result;
    }
    
    /**
     * Calculate the height of the tree
     */
    int height() {
        return heightRecursive(root);
    }
    
    /**
     * Validate that the tree maintains BST property
     */
    bool isValidBST() {
        return validateBST(root, LONG_MIN, LONG_MAX);
    }
    
    /**
     * Get the size of the tree
     */
    int size() const {
        return treeSize;
    }
    
    /**
     * Check if the tree is empty
     */
    bool isEmpty() const {
        return root == nullptr;
    }
};

/**
 * Demonstrate BST operations with examples
 */
void demonstrateBST() {
    cout << "=== Binary Search Tree Demo ===" << endl;
    BinarySearchTree bst;
    
    cout << "Inserting values: 50, 30, 70, 20, 40, 60, 80" << endl;
    
    // Insert values to create a balanced tree
    vector<int> values = {50, 30, 70, 20, 40, 60, 80};
    for (int value : values) {
        bst.insert(value);
    }
    
    cout << "\nTree size: " << bst.size() << endl;
    cout << "Tree height: " << bst.height() << endl;
    cout << "Is valid BST: " << (bst.isValidBST() ? "true" : "false") << endl;
    
    // Search operations
    cout << "\n=== Search Operations ===" << endl;
    vector<int> searchValues = {40, 25, 70, 100};
    for (int value : searchValues) {
        TreeNode* result = bst.search(value);
        string status = (result != nullptr) ? "Found" : "Not found";
        cout << "Search " << value << ": " << status << endl;
    }
    
    // Tree traversal
    cout << "\n=== Tree Traversal ===" << endl;
    vector<int> inorder = bst.inorderTraversal();
    cout << "Inorder traversal (sorted): ";
    for (size_t i = 0; i < inorder.size(); i++) {
        cout << inorder[i];
        if (i < inorder.size() - 1) cout << ", ";
    }
    cout << endl;
    
    // Min/Max values
    try {
        cout << "\nMinimum value: " << bst.findMin() << endl;
        cout << "Maximum value: " << bst.findMax() << endl;
    } catch (const runtime_error& e) {
        cout << "Error: " << e.what() << endl;
    }
}

int main() {
    demonstrateBST();
    return 0;
} 

Key Takeaways

When to Use BSTs

• Dynamic Data: When the dataset size changes frequently
• Sorted Access: Need to frequently access data in sorted order
• Range Queries: Finding elements within a specific range
• Fast Lookups: When O(log n) search performance is required
• No Index Access: When random index access is not needed

BST Applications

• Database Indexing: B-trees (BST variants) for efficient data retrieval
• Expression Parsing: Building syntax trees for compilers
• File Systems: Directory structures and file organization
• Priority Queues: When combined with heap properties
• Symbol Tables: Variable lookup in programming languages