Tree Sort in Java

Yasin Cakal

Tree sort is a sorting algorithm that utilizes a binary tree data structure to arrange elements. It is a comparison-based sorting algorithm, meaning it uses comparison operators to compare two elements to determine which is larger or smaller. Tree sort is a stable sorting algorithm, which means it preserves the order of equal elements.

Tree sort is useful for sorting large datasets efficiently and quickly. It has a simple implementation and is easy to understand. This makes it a great choice for beginners who are just starting to learn about sorting algorithms.

How Tree Sort Works

Tree sort works by first creating a binary tree data structure. A binary tree is a tree-like structure in which each node can only have two children. The root node is the node at the top of the tree and all other nodes are either children of the root node or descendants of the root node.

To create a binary tree, we start with an empty tree and add elements one by one. Each element is added to the tree as a node and is then connected to the root node. The elements are sorted in the tree by comparing each element to the root node and placing it in the correct position relative to the root node.

Once the tree is complete, the elements can be sorted by traversing the tree in a pre-order traversal. This means that the root node is visited first, then its left child, then its right child, and so on. This process continues until all of the elements have been visited and sorted in the correct order.

Time Complexity

The time complexity of tree sort depends on the size of the dataset. For a dataset of size n, it takes O(n log n) time to create the tree and O(n) time to sort it.

The time complexity for accessing, searching, insertion, and deletion is also O(n log n). This is because each of these operations requires traversing the tree from the root node, which takes O(log n) time.

Space Complexity

The space complexity of tree sort is O(n). This is because the tree must store all of the elements in the dataset.

Java Code

Here is an example of tree sort in Java:

public class TreeSort {
    public static void main(String[] args) {
        int[] array = {3, 5, 7, 1, 2, 4, 6};
 
        // Create a binary tree
        TreeNode root = new TreeNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.add(array[i]);
        }
 
        // Traverse the tree in pre-order
        root.preOrder();
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int data) {
        this.data = data;
    }
 
    public void add(int data) {
        if (data < this.data) {
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                this.left.add(data);
            }
        } else {
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                this.right.add(data);
            }
        }
    }
 
    public void preOrder() {
        System.out.println(this.data);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
}

Conclusion

Tree sort is a comparison-based sorting algorithm that uses a binary tree data structure to arrange elements. It is a stable sorting algorithm and has a time complexity of O(n log n). It is a great choice for sorting large datasets efficiently and quickly. With a bit of practice, it is not difficult to understand and implement tree sort in Java.

Exercises

Write a program to create a binary tree from a given array of integers.

public class TreeSort {
    public static void main(String[] args) {
        int[] array = {3, 5, 7, 1, 2, 4, 6};
 
        // Create a binary tree
        TreeNode root = new TreeNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.add(array[i]);
        }
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int data) {
        this.data = data;
    }
 
    public void add(int data) {
        if (data < this.data) {
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                this.left.add(data);
            }
        } else {
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                this.right.add(data);
            }
        }
    }
}

Write a program to traverse a binary tree in pre-order.

public class TreeSort {
    public static void main(String[] args) {
        // Create a binary tree
        TreeNode root = new TreeNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.add(array[i]);
        }
 
        // Traverse the tree in pre-order
        root.preOrder();
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int data) {
        this.data = data;
    }
 
    public void add(int data) {
        if (data < this.data) {
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                this.left.add(data);
            }
        } else {
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                this.right.add(data);
            }
        }
    }
 
    public void preOrder() {
        System.out.println(this.data);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
}

Write a program to insert a new node into a binary tree.

public class TreeSort {
    public static void main(String[] args) {
        // Create a binary tree
        TreeNode root = new TreeNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.add(array[i]);
        }
 
        // Insert a new node
        int newData = 8;
        root.insert(newData);
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int data) {
        this.data = data;
    }
 
    public void add(int data) {
        if (data < this.data) {
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                this.left.add(data);
            }
        } else {
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                this.right.add(data);
            }
        }
    }
 
    public void insert(int data) {
        // Check if data is less than the current node's data
        if (data < this.data) {
            // If there is no left child, create a new node
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                // Otherwise, recursively call insert on the left child
                this.left.insert(data);
            }
        } else {
            // If there is no right child, create a new node
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                // Otherwise, recursively call insert on the right child
                this.right.insert(data);
            }
        }
    }
}

Write a program to delete a node from a binary tree.

public class TreeSort {
    public static void main(String[] args) {
        // Create a binary tree
        TreeNode root = new TreeNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.add(array[i]);
        }
 
        // Delete a node
        int data = 2;
        root.delete(data);
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int data) {
        this.data = data;
    }
 
    public void add(int data) {
        if (data < this.data) {
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                this.left.add(data);
            }
        } else {
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                this.right.add(data);
            }
        }
    }
 
    public void delete(int data) {
        // Check if the data is less than the current node's data
        if (data < this.data) {
            // If there is a left child, recursively call delete on the left child
            if (this.left != null) {
                this.left.delete(data);
            }
        } else if (data > this.data) {
            // If there is a right child, recursively call delete on the right child
            if (this.right != null) {
                this.right.delete(data);
            }
        } else {
            // If the data is equal to the current node's data, delete the node
            if (this.left != null && this.right != null) {
                // If the node has two children, set the node's data to the data of its in-order predecessor
                TreeNode predecessor = this.left.findMax();
                this.data = predecessor.data;
                this.left.delete(predecessor.data);
            } else if (this.left != null) {
                // If the node has only a left child, set the node's left child to be the node's parent
                this.data = this.left.data;
                this.left = this.left.left;
            } else if (this.right != null) {
                // If the node has only a right child, set the node's right child to be the node's parent
                this.data = this.right.data;
                this.right = this.right.right;
            } else {
                // If the node has no children, set the node's parent to null
                this.data = 0;
            }
        }
    }
 
    public TreeNode findMax() {
        if (this.right == null) {
            return this;
        } else {
            return this.right.findMax();
        }
    }
}

Write a program to search for a node in a binary tree.

public class TreeSort {
    public static void main(String[] args) {
        // Create a binary tree
        TreeNode root = new TreeNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.add(array[i]);
        }
 
        // Search for a node
        int data = 7;
        TreeNode node = root.search(data);
        if (node != null) {
            System.out.println("Found node with data: " + node.data);
        } else {
            System.out.println("Node not found");
        }
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int data) {
        this.data = data;
    }
 
    public void add(int data) {
        if (data < this.data) {
            if (this.left == null) {
                this.left = new TreeNode(data);
            } else {
                this.left.add(data);
            }
        } else {
            if (this.right == null) {
                this.right = new TreeNode(data);
            } else {
                this.right.add(data);
            }
        }
    }
 
    public TreeNode search(int data) {
        // Check if the data is equal to the current node's data
        if (data == this.data) {
            return this;
        } else if (data < this.data) {
            // If there is a left child, recursively call search on the left child
            if (this.left != null) {
                return this.left.search(data);
            }
        } else {
            // If there is a right child, recursively call search on the right child
            if (this.right != null) {
                return this.right.search(data);
            }
        }
        // Return null if the node is not found
        return null;
    }
}

Data Structures and Algorithms with Java

Participants 433