In this post, We will learn How to perform insert operation in a binary search tree?
The insert method:
We insert an element at the place where we ‘fall off’ the tree looking for it.
To insert key into Tree t:
• If t is empty, replace t by a tree consisting of a single node with value key.
• If t has key at its root, key is already in t. Return without modifying t.
• If key is less than the value at the root of t, insert key into the left subtree
of t.
• If key is greater than the value at the root of t, insert key into the right
subtree of t.
Inserting a node requires a change to its parent. In our recursion logic, we have to pass information back to the parent so it can change itself.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
/** * Insert operation in binary tree * @param data to insert */ public void insert(E data) { root = insert(root, data); } private static <T extends Comparable<? super T>> Node<T> insert(Node<T> node, T data) { if (node == null) { node = new Node<T>(data); } else if (data.compareTo(node.data) < 0) { node.left = insert(node.left, data); } else if (data.compareTo(node.data) > 0) { node.right = insert(node.right, data); } return node; } |
Complete Souce code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
package com.kkjavatutorials.tree; public class BinaryTree<E extends Comparable<? super E>> { //Root of Binary Tree private Node<E> root; /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for preOrder Processing * @param root Node */ public void preOrder(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } /** * Insert operation in binary search tree * @param data to insert */ public void insert(E data) { root = insert(root, data); } private static <T extends Comparable<? super T>> Node<T> insert(Node<T> node, T data) { if (node == null) { node = new Node<T>(data); } else if (data.compareTo(node.data) < 0) { node.left = insert(node.left, data); } else if (data.compareTo(node.data) > 0) { node.right = insert(node.right, data); } return node; } public Node<E> getRoot() { return root; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package com.kkjavatutorials.client; import com.kkjavatutorials.tree.BinaryTree; /** * Client Program to test insert operation in Binary search Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); binaryTree.insert(10); binaryTree.insert(15); binaryTree.insert(5); binaryTree.insert(40); binaryTree.insert(80); //Call for preOrder processing System.out.println("Output of preOrder processing of Binary Search Tree"); binaryTree.preOrder(binaryTree.getRoot()); } } |
The output of This Program:
Output of preOrder processing of Binary Search Tree
10 5 15 40 80
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Delete operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
That’s all about Insert operation in a binary search tree?
If you have any feedback or suggestion please feel free to drop in below comment box.