BINARY SEARCH TREES(BST)

A Binary search tree (BST) is a data structure where each node has two references – left and right. The value in the left reference is less than the value in the node and the value in the right reference is more than the value in the node. Typically, all values in a binary search tree are distinct. The node at the top of a BST is called the root.

To access any node in a BST, we will need to know one of the following:

· The address of the node

· The address of the parent of the node

· Node.java: Implements the class for a single node in a BST

· Tree.java: Implements the class for creating a BST

· TestTree.java: Uses the Tree class to create and insert values to a BST.

Example:

Binary Search Trees

1 - Insert a Value

2 - Print the Tree

3 - Quit

1

Input Value

34

1 - Insert a Value

2 - Print the Tree

3 - Quit

1

Input Value

89

1 - Insert a Value

2 - Print the Tree

3 - Quit

2

89

34

1 - Insert a Value

2 - Print the Tree

3 - Quit

1

Input Value

9

1 - Insert a Value

2 - Print the Tree

3 - Quit

1

Input Value

0

1 - Insert a Value

2 - Print the Tree

3 - Quit

2

89

34

9

0

1 - Insert a Value

2 - Print the Tree

3 - Quit

1

Input Value

123

1 - Insert a Value

2 - Print the Tree

3 - Quit

1

Input Value

56

1 - Insert a Value

2 - Print the Tree

3 - Quit

2

123

89

56

34

9

0

1 - Insert a Value

2 - Print the Tree

3 - Quit

3

End of Program