Binary Trees II: Guided Project

Implementation Steps

1. 1

   Implement Search Method

   Create a recursive search method that leverages the BST property

   public boolean search(int value) {
       return searchRecursive(root, value);
   }
   
   private boolean searchRecursive(Node node, int value) {
       // Base case: Empty tree or value found
       if (node == null) {
           return false;
       }
       
       if (node.getValue() == value) {
           return true;
       }
       
       // Recursive case: Search left or right subtree
       if (value < node.getValue()) {
           return searchRecursive(node.getLeft(), value);
       } else {
           return searchRecursive(node.getRight(), value);
       }
   }

2. 2

   Implement In-Order Traversal

   Create a method to traverse the tree in-order (left, root, right)

   public void inOrderTraversal() {
       inOrderTraversalHelper(root);
   }
   
   private void inOrderTraversalHelper(Node node) {
       if (node == null) {
           return;
       }
       
       // Visit left subtree
       inOrderTraversalHelper(node.getLeft());
       
       // Visit current node
       System.out.print(node.getValue() + " ");
       
       // Visit right subtree
       inOrderTraversalHelper(node.getRight());
   }

3. 3

   Implement Pre-Order and Post-Order Traversals

   Create methods for the other common traversal patterns

   public void preOrderTraversal() {
       preOrderTraversalHelper(root);
   }
   
   private void preOrderTraversalHelper(Node node) {
       if (node == null) {
           return;
       }
       
       // Visit current node first
       System.out.print(node.getValue() + " ");
       
       // Then visit subtrees
       preOrderTraversalHelper(node.getLeft());
       preOrderTraversalHelper(node.getRight());
   }
   
   public void postOrderTraversal() {
       postOrderTraversalHelper(root);
   }
   
   private void postOrderTraversalHelper(Node node) {
       if (node == null) {
           return;
       }
       
       // Visit subtrees first
       postOrderTraversalHelper(node.getLeft());
       postOrderTraversalHelper(node.getRight());
       
       // Visit current node last
       System.out.print(node.getValue() + " ");
   }

Visual Explanation: Search Process

Let's visualize how search works in a BST. Consider searching for the value 7 in this tree:

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

Step 1: Start at the Root (10)

7 < 10, so go left

Step 2: Examine Node 5

7 > 5, so go right

Step 3: Examine Node 7

7 == 7, found the target value! Return true.

Traversal Patterns

For the tree above:

• In-Order: 3, 5, 7, 10, 12, 15, 17 (sorted order!)
• Pre-Order: 10, 5, 3, 7, 15, 12, 17 (root first, then children)
• Post-Order: 3, 7, 5, 12, 17, 15, 10 (children first, then root)

Iterative Implementation

For better space efficiency, you can implement search and traversals iteratively using a stack:

Iterative Search

public boolean searchIterative(int value) {
    Node current = root;
    
    while (current != null) {
        if (current.getValue() == value) {
            return true;
        }
        
        if (value < current.getValue()) {
            current = current.getLeft();
        } else {
            current = current.getRight();
        }
    }
    
    return false;
}

Iterative In-Order Traversal

public void inOrderIterative() {
    if (root == null) return;
    
    Stack stack = new Stack<>();
    Node current = root;
    
    while (current != null || !stack.isEmpty()) {
        // Go left as far as possible
        while (current != null) {
            stack.push(current);
            current = current.getLeft();
        }
        
        // Process the node
        current = stack.pop();
        System.out.print(current.getValue() + " ");
        
        // Go right
        current = current.getRight();
    }
}

Advanced Operations: Finding Predecessor and Successor

In a BST, finding the in-order predecessor or successor of a node can be useful for many operations:

Finding Successor

public Node findSuccessor(Node node) {
    // If right subtree exists, find the minimum value in it
    if (node.getRight() != null) {
        return findMin(node.getRight());
    }
    
    // Otherwise, find the nearest ancestor where node is in its left subtree
    Node successor = null;
    Node current = root;
    
    while (current != null) {
        if (node.getValue() < current.getValue()) {
            successor = current;
            current = current.getLeft();
        } else if (node.getValue() > current.getValue()) {
            current = current.getRight();
        } else {
            break; // Found the node
        }
    }
    
    return successor;
}

private Node findMin(Node node) {
    while (node.getLeft() != null) {
        node = node.getLeft();
    }
    return node;
}

Exercise 1: Search Implementation

Implement a search method that returns true if a value exists in the BST, false otherwise.

public boolean search(int value) {
    // Your implementation here
}

Exercise 2: Tree Traversal

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

public void inOrderTraversal() {
    // Your implementation here
}

Exercise 3: Level Order Traversal

Implement level-order (breadth-first) traversal to visit all nodes level by level.

public void levelOrderTraversal() {
    if (root == null) return;
    
    Queue queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        // Your implementation here
        // Hint: Use a queue data structure
    }
}

Exercise 4: Count Nodes

Write a method to count the total number of nodes in the BST.

public int countNodes() {
    // Your implementation here
    // Hint: Can use any traversal method
}

Exercise 5: Advanced - Lowest Common Ancestor

Implement a method to find the lowest common ancestor (LCA) of two nodes in the BST.

public Node findLCA(int value1, int value2) {
    // Your implementation here
    // Hint: Use the BST property to determine which subtree to search
}

Exercise 6: Delete Node

Implement the delete operation for a BST. This is more complex than insertion or search.

public void delete(int value) {
    root = deleteRecursive(root, value);
}

private Node deleteRecursive(Node root, int value) {
    // Your implementation here
    // Cases to handle:
    // 1. Node is a leaf
    // 2. Node has one child
    // 3. Node has two children (find in-order successor)
}