# Java/Binary Search Trees

### From charlesreid1

## Binary Search Tree Class

For more details about the binary search tree abstract data type, see Binary Search Trees/ADT.

For more details about all abstract data types, see Abstract Data Types.

The binary search tree type is a generally useful data container that can be implemented multiple ways. The real goal here is to keep the implementation of the binary tree abstract data type lightweight and uncomplicated.

## Organization

The organization of the binary search tree abstract data type class is as follows:

- BinaryNode class to represent nodes in the binary tree (the binary tree class owns this class and manipulates these binary nodes directly).
- Constructor to create empty tree
- Insert method to add items to the binary tree
- Remove method to remove items from the binary tree
- Contains/Search method to find items in binary tree
- findMin/findMax methods to find minimum and maximum elements in trees/subtrees

These methods are all implemented with recursion.

## Binary Node Class

Here is the binary node class - again, kept simple, with the focus being on the implementation/application and not on extra features:

class BinaryNode { Integer element; BinaryNode left, right; public BinaryNode(Integer e, BinaryNode l, BinaryNode r) { this.left = l; this.right = r; this.element = e; } public String toString() { return this.element.toString(); } public Integer getElement() { return this.element; } public void setElement(Integer e) { this.element = e; } public BinaryNode getLeft() { return this.left; } public BinaryNode getRight() { return this.right; } public void setLeft(BinaryNode newChild) { this.left = newChild; } public void setRight(BinaryNode newChild) { this.left = newChild; } }

## Driver

A driver utilizing the binary search tree would look something like this:

## Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |