Java Data Structures and Algorithms for Beginners

Tree Data Structure

Definition and Concepts

A tree is a hierarchical data structure consisting of nodes connected by edges, with a single root node at the top and no cycles. Each node can have zero or more child nodes, and every node except the root has exactly one parent. In a Binary Search Tree (BST), which is a common type of tree, each node has at most two children (left and right), and the left subtree contains values less than the node’s value, while the right subtree contains values greater. Trees are used to represent hierarchical relationships and enable efficient searching, insertion, and deletion. You can visualize a tree as a family tree, where each person (node) has descendants (children) and an ancestor (parent).

Why Use It?

Trees are used to organize data hierarchically, enabling efficient operations like searching, insertion, and deletion with an average time complexity of O(log n) in a balanced BST. They are ideal for applications requiring ordered data, dynamic updates, or hierarchical structures. Trees provide a natural way to represent relationships, such as organizational charts or file systems, and are foundational for advanced data structures like heaps and tries.

Where to Use? (Real-Life Examples)

• File Systems: Operating systems use trees to represent directory structures, where folders are nodes and subfolders or files are children.
• Database Indexing: Databases use trees (e.g., B-trees or BSTs) to index data, enabling fast searches and range queries.
• Expression Parsing: Compilers use expression trees to represent mathematical expressions, such as (2 + 3) * 4, for evaluation.
• Autocomplete Systems: Search engines use trie (a type of tree) to store words for efficient prefix-based suggestions.

Explain Operations

• Insert: This operation adds a new node with a given value to the tree while maintaining the BST property. It has an average time complexity of O(log n) in a balanced tree.
• Search: This operation finds a node with a given value by traversing left or right based on comparisons. It has an average time complexity of O(log n).
• Delete: This operation removes a node with a given value, adjusting the tree to maintain the BST property. It has an average time complexity of O(log n).
• Inorder Traversal: This operation visits nodes in sorted order (left, root, right). It has a time complexity of O(n).
• isEmpty: This operation checks whether the tree is empty. It has a time complexity of O(1).

Java Implementation

The following Java code implements a Binary Search Tree with basic operations.

public class BinarySearchTree {
    private class Node {
        int value; // Value stored in the node
        Node left; // Reference to the left child
        Node right; // Reference to the right child

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    private Node root; // Root of the BST
    private int size; // Number of nodes in the tree

    // Constructor to initialize an empty BST
    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    // Insert: Adds a new value to the BST
    public void insert(int value) {
        root = insertRec(root, value); // Recursively inserts the value
        size++; // Increments the size
    }

    private Node insertRec(Node root, int value) {
        if (root == null) { // If the subtree is empty, create a new node
            return new Node(value);
        }
        if (value < root.value) { // Inserts into left subtree if value is smaller
            root.left = insertRec(root.left, value);
        } else if (value > root.value) { // Inserts into right subtree if value is larger
            root.right = insertRec(root.right, value);
        }
        return root; // Returns unchanged root if value already exists
    }

    // Search: Checks if a value exists in the BST
    public boolean search(int value) {
        return searchRec(root, value); // Recursively searches for the value
    }

    private boolean searchRec(Node root, int value) {
        if (root == null || root.value == value) { // Returns true if found, false if null
            return root != null;
        }
        if (value < root.value) { // Searches left subtree if value is smaller
            return searchRec(root.left, value);
        }
        return searchRec(root.right, value); // Searches right subtree if value is larger
    }

    // Delete: Removes a value from the BST
    public void delete(int value) {
        root = deleteRec(root, value); // Recursively deletes the value
        size--; // Decrements the size
    }

    private Node deleteRec(Node root, int value) {
        if (root == null) { // If value not found, return null
            return null;
        }
        if (value < root.value) { // Deletes from left subtree if value is smaller
            root.left = deleteRec(root.left, value);
        } else if (value > root.value) { // Deletes from right subtree if value is larger
            root.right = deleteRec(root.right, value);
        } else { // Node to delete found
            if (root.left == null) { // Case 1: No left child, return right child
                return root.right;
            } else if (root.right == null) { // Case 2: No right child, return left child
                return root.left;
            }
            // Case 3: Two children, replace with successor
            root.value = findMin(root.right).value; // Replaces with minimum in right subtree
            root.right = deleteRec(root.right, root.value); // Deletes the successor
        }
        return root;
    }

    // Helper method to find the minimum value node in a subtree
    private Node findMin(Node root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    // Inorder Traversal: Prints nodes in sorted order
    public void inorder() {
        inorderRec(root); // Recursively traverses the tree
        System.out.println(); // Adds newline after traversal
    }

    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left); // Visits left subtree
            System.out.print(root.value + " "); // Visits current node
            inorderRec(root.right); // Visits right subtree
        }
    }

    // isEmpty: Checks if the BST is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Size: Returns the number of nodes in the BST
    public int size() {
        return size;
    }
}

How It Works

1. Initialization: The constructor initializes the root as null and size as 0, indicating an empty Binary Search Tree.
2. Insert Operation:
   • The method recursively traverses the tree based on the value: left if the value is smaller, right if larger.
   • If an empty spot is found (null node), it creates a new node with the value.
   • The size is incremented for each new node.
3. Search Operation:
   • The method recursively traverses the tree, comparing the target value with the current node’s value.
   • It returns true if the value is found or false if a null node is reached.
4. Delete Operation:
   • The method finds the node to delete by traversing left or right based on the value.
   • It handles three cases: no children (return null), one child (return the child), or two children (replace with the minimum value from the right subtree and delete that node).
   • The size is decremented after deletion.
5. Inorder Traversal: The method recursively visits the left subtree, the current node, and the right subtree, printing values in sorted order.
6. isEmpty Operation: The method returns true if size equals 0, indicating an empty tree, and false otherwise.
7. Size Operation: The method returns size, which represents the number of nodes in the tree.
8. FindMin Helper: This method finds the smallest value in a subtree by traversing left until a null left child is reached.

Complexity Analysis Table

Note: Worst-case time complexity occurs in an unbalanced tree (e.g., a skewed tree resembling a linked list).

Key Differences / Notes

• Binary Search Tree vs. Other Trees:
  • The implementation above is a BST, where nodes are ordered for efficient searching. Other trees include binary trees (no ordering), AVL trees (self-balancing), and B-trees (for databases).
  • AVL and Red-Black trees maintain balance to ensure O(log n) operations, unlike a BST, which can degrade to O(n) if unbalanced.
• Balancing: The provided BST is not self-balancing, which can lead to poor performance if insertions are not random. Use AVL or Red-Black trees for guaranteed balance.
• Thread Safety: The implementation is not thread-safe. For concurrent applications, use synchronized methods or Java’s ConcurrentSkipListMap for a tree-like structure.
• Java’s Built-in Trees: Java provides TreeMap and TreeSet in java.util, which are implemented as Red-Black trees for balanced performance.

✅ Tip: Use a self-balancing tree like AVL or Red-Black for applications requiring consistent O(log n) performance, especially with frequent insertions or deletions.

⚠ Warning: An unbalanced BST can degrade to O(n) performance if insertions occur in sorted order, resembling a linked list. Always consider input patterns when using a BST.

Exercises

1. BST Validator: Write a Java program that checks if a given tree is a valid Binary Search Tree by ensuring all nodes follow the BST property. Test it with at least three different trees.
2. Height of BST: Extend the BST implementation to include a method that computes the height of the tree. Test it with balanced and unbalanced trees.
3. Range Sum Query: Create a program that uses the BST to find the sum of all values within a given range (e.g., between 20 and 60). Use inorder traversal to collect values.
4. Preorder and Postorder Traversals: Add methods to the BST implementation for preorder (root, left, right) and postorder (left, right, root) traversals. Print the results for a sample tree.
5. Lowest Common Ancestor: Implement a method to find the lowest common ancestor of two nodes in the BST. Test it with different pairs of values.