Binary Trees I: Guided Project

Implementation Steps

1. 1

   Create Node Class

   Define a Node class with value, left, and right properties

   public class Node {
       private int value;
       private Node left;
       private Node right;
       
       public Node(int value) {
           this.value = value;
           this.left = null;
           this.right = null;
       }
       
       // Getters and setters
       public int getValue() { return value; }
       public Node getLeft() { return left; }
       public Node getRight() { return right; }
       public void setLeft(Node left) { this.left = left; }
       public void setRight(Node right) { this.right = right; }
   }

2. 2

   Implement BST Class

   Create a Binary Search Tree class with a root node reference

   public class BinarySearchTree {
       private Node root;
       
       public BinarySearchTree() {
           this.root = null;
       }
       
       // Public insert method
       public void insert(int value) {
           root = insertRecursive(root, value);
       }
       
       // Private recursive helper
       private Node insertRecursive(Node current, int value) {
           // Base case: If current is null, create a new node
           if (current == null) {
               return new Node(value);
           }
           
           // Recursive case: Traverse left or right
           if (value < current.getValue()) {
               current.setLeft(insertRecursive(current.getLeft(), value));
           } else if (value > current.getValue()) {
               current.setRight(insertRecursive(current.getRight(), value));
           }
           
           // Return the (possibly modified) node reference
           return current;
       }
   }

3. 3

   Handle Edge Cases

   Consider how to handle duplicates, depending on your requirements:

   // Option 1: Ignore duplicates (shown above)
   // Option 2: Allow duplicates (e.g., go to the right)
   if (value >= current.getValue()) {
       current.setRight(insertRecursive(current.getRight(), value));
   }
   
   // Option 3: Track frequency with a count field
   if (value == current.getValue()) {
       current.incrementCount(); // Assuming a count field exists
       return current;
   }

Visual Explanation: Insertion Process

Let's visualize how insertion works by inserting values [10, 5, 15, 3, 7, 12, 17] in order:

1. Insert 10 (root)

       10

2. Insert 5 (less than 10, go left)

       10
       /
      5

3. Insert 15 (greater than 10, go right)

       10
       / \
      5   15

4. Insert 3 (less than 10, go left; less than 5, go left)

       10
       / \
      5   15
     /
    3

5. Insert 7 (less than 10, go left; greater than 5, go right)

       10
       / \
      5   15
     / \
    3   7

6. Final tree after inserting 12 and 17

       10
       / \
      5   15
     / \  / \
    3   7 12 17

Notice how each insertion follows the BST property: values less than a node go to its left, values greater go to its right.

Performance Considerations

• Time Complexity: O(log n) for balanced trees, but can degrade to O(n) in worst case (when tree becomes a linked list)
• Space Complexity: O(h) where h is the height of the tree (due to recursion stack)
• Balancing: Standard BSTs can become unbalanced. Consider self-balancing trees like AVL or Red-Black trees for guaranteed O(log n) operations.

Implementation Variations

Iterative Insert (Non-Recursive)

public void insertIterative(int value) {
    Node newNode = new Node(value);
    
    // If tree is empty, set new node as root
    if (root == null) {
        root = newNode;
        return;
    }
    
    // Traverse to find the insertion point
    Node current = root;
    Node parent = null;
    
    while (true) {
        parent = current;
        
        if (value < current.getValue()) {
            current = current.getLeft();
            if (current == null) {
                parent.setLeft(newNode);
                return;
            }
        } else {
            current = current.getRight();
            if (current == null) {
                parent.setRight(newNode);
                return;
            }
        }
    }
}

Exercise 1: Basic Insertion

Implement the insert method for a Binary Search Tree that maintains the BST property.

public void insert(int value) {
    // Your implementation here
}

Exercise 2: Tree Validation

Write a method to verify if a binary tree satisfies the BST property.

public boolean isValidBST() {
    return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValidBSTHelper(Node node, int min, int max) {
    // Your implementation here
    // Hint: Each node's value must be within the valid range for its position
}

Exercise 3: Tree Traversal

Implement in-order traversal to print all values in sorted order.

public void inOrderTraversal() {
    inOrderTraversalHelper(root);
}

private void inOrderTraversalHelper(Node node) {
    // Your implementation here
    // Hint: Visit left subtree, then node, then right subtree
}

Exercise 4: Find Min and Max Values

Implement methods to find the minimum and maximum values in the BST.

public int findMin() {
    // Your implementation here
    // Hint: Keep going left until you can't go anymore
}

public int findMax() {
    // Your implementation here
    // Hint: Keep going right until you can't go anymore
}

Exercise 5: Advanced - Tree Height

Implement a method to calculate the height of the tree (the length of the longest path from root to leaf).

public int height() {
    return heightHelper(root);
}

private int heightHelper(Node node) {
    // Your implementation here
    // Hint: Use recursion to find the maximum height of the left and right subtrees
}