Binary Search Tree!
What is Binary Search Tree?
Binary Search Tree is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.
Following are the basic operations of a tree −
- Search − Searches an element in a tree.
- Insert − Inserts an element in a tree.
- Pre-order Traversal − Traverses a tree in a pre-order manner.
- In-order Traversal − Traverses a tree in an in-order manner.
- Post-order Traversal − Traverses a tree in a post-order manner.
In Binary Search Tree every node can have at most two children. We usually refer to these two children by their position relative to the parent. We usually restrict the number of children a binary search tree node can have. Also, We restrict the value of every node in the structure. In the example above, you can see the value of every left node is less than the parent node.
One of the biggest challenges or the most asked question you will find to answer is exactly how to add new nodes to an existing binary search tree. To answer this question you will have to see the value you have to add if it’s less or grater than the parent node. If it’s less than you have to add to the left side, if it’s grater you have to add to the right side.
Below is an example of a Binary Search Tree construction:
Directions:
- Implement the Node class to class to create a binary search tree. The constructor should initialize values ‘data’, ‘left’, and ‘right’.
- Implement the ‘insert’ method for the node class. Insert should accept an argument ‘data’, then create an insert a new node at the appropriate location in the tree.
- Implement the ‘contains method for the Node class. Contains should accept a ‘data’ argument and return the Node in the tree with the same value. If the value isn’t in the tree return null.
