Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // A utility function to search a given key in BST
- public Node search(Node root, int key)
- {
- // Base Cases: root is null or key is present at root
- if (root==null || root.key==key)
- return root;
- // val is greater than root's key
- if (root.key > key)
- return search(root.left, key);
- // val is less than root's key
- return search(root.right, key);
- }
- Illustration to search 6 in below tree:
- 1. Start from root.
- 2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
- 3. If element to search is found anywhere, return true, else return false.
- bstsearch
- Insertion of a key
- A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
- 100 100
- / \ Insert 40 / \
- 20 500 ---------> 20 500
- / \ / \
- 10 30 10 30
- \
- 40
- filter_none
- edit
- play_arrow
- brightness_4
- // Java program to demonstrate insert operation in binary search tree
- class BinarySearchTree {
- /* Class containing left and right child of current node and key value*/
- class Node {
- int key;
- Node left, right;
- public Node(int item) {
- key = item;
- left = right = null;
- }
- }
- // Root of BST
- Node root;
- // Constructor
- BinarySearchTree() {
- root = null;
- }
- // This method mainly calls insertRec()
- void insert(int key) {
- root = insertRec(root, key);
- }
- /* A recursive function to insert a new key in BST */
- Node insertRec(Node root, int key) {
- /* If the tree is empty, return a new node */
- if (root == null) {
- root = new Node(key);
- return root;
- }
- /* Otherwise, recur down the tree */
- if (key < root.key)
- root.left = insertRec(root.left, key);
- else if (key > root.key)
- root.right = insertRec(root.right, key);
- /* return the (unchanged) node pointer */
- return root;
- }
- // This method mainly calls InorderRec()
- void inorder() {
- inorderRec(root);
- }
- // A utility function to do inorder traversal of BST
- void inorderRec(Node root) {
- if (root != null) {
- inorderRec(root.left);
- System.out.println(root.key);
- inorderRec(root.right);
- }
- }
- // Driver Program to test above functions
- public static void main(String[] args) {
- BinarySearchTree tree = new BinarySearchTree();
- /* Let us create following BST
- 50
- / \
- 30 70
- / \ / \
- 20 40 60 80 */
- tree.insert(50);
- tree.insert(30);
- tree.insert(20);
- tree.insert(40);
- tree.insert(70);
- tree.insert(60);
- tree.insert(80);
- // print inorder traversal of the BST
- tree.inorder();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement