Guided Project: Binary Trees I

Project Overview

Learning Goals

Understand BST insertion algorithm
Implement node insertion logic
Maintain BST properties
Handle edge cases properly

Prerequisites

Binary Tree basics
BST properties understanding
Basic recursive concepts
JavaScript fundamentals

Binary Search Tree Insert

Implementation Steps

Step 1: Node Creation

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

Step 2: Insert Method

                                    public void insert(int value) {
    BSTNode newNode = new BSTNode(value);
    if (root == null) {
        root = newNode;
        return;
    }
    insertNode(root, newNode);
}
                                

Step 3: Recursive Insert Helper

                                private void insertNode(BSTNode node, BSTNode newNode) {
    if (newNode.value < node.value) {
        if (node.left == null) {
            node.left = newNode;
        } else {
            insertNode(node.left, newNode);
        }
    } else {
        if (node.right == null) {
            node.right = newNode;
        } else {
            insertNode(node.right, newNode);
        }
    }
}
                            

Step 4: Complete BST Class

                                class BST {
    BSTNode root;
    public BST() {
        this.root = null;
    }
    public void insert(int value) {
        BSTNode newNode = new BSTNode(value);
        if (root == null) {
            root = newNode;
            return;
        }
        insertNode(root, newNode);
    }
    private void insertNode(BSTNode node, BSTNode newNode) {
        if (newNode.value < node.value) {
            if (node.left == null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right == null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    }
}
                            

Practice Challenge

Now that you've learned how to implement BST insertion, try extending your knowledge with this practice challenge.

Challenge: Implement BST Search

Implement a method called search(value) for the BST class that checks if a value exists in the tree.

Requirements:

The method should return true if the value is found in the tree
The method should return false if the value is not in the tree
Optimize your solution to take advantage of BST properties

Starter Code:

                            class BST {
    BSTNode root;
    public BST() {
        this.root = null;
    }
    // Previous methods here...
    public boolean search(int value) {
        return searchRecursive(root, value);
    }
    private boolean searchRecursive(BSTNode node, int value) {
        if (node == null) {
            return false;
        }
        if (node.value == value) {
            return true;
        }
        if (value < node.value) {
            return searchRecursive(node.left, value);
        } else {
            return searchRecursive(node.right, value);
        }
    }
}
                        

Challenge Practice Resources:

If you want more practice with Binary Search Trees, check out these LeetCode problems: