Java Program to Implement Binary Tree
What is a Binary Tree?
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Each node in a binary tree has a value and a pointer to the left and right child nodes. The topmost node in a binary tree is called the root. The left subtree of a node contains only nodes with keys lesser than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key. The leaves of a binary tree, which have no children, are often used to represent the end of a sequence of operations or data.
Steps to Implement Binary Tree Data Structure :
1. Define a class Node that will represent each node in the tree. The class should have the following properties:
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
2. Define a class BinaryTree that will represent the binary tree as a whole. The class should have the following properties:
- A pointer to the root node
- Methods for inserting new nodes into the tree
- Methods for traversing the tree in different ways (e.g. in-order, pre-order, post-order)
class BinaryTree {
Node root;
BinaryTree() {
root = null;
}
3. Implement the insert method in the BinaryTree class.
This method should take in an integer value (the key of the new node) and insert it into the tree in the appropriate location. You can implement this method using a recursive helper function called insertRec. This helper function should take in the current root node and the key to be inserted, and return the updated root node after the insertion.
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
4. Implement the inorder method in the BinaryTree class.
This method should traverse the tree in an in-order fashion (i.e. visiting the left subtree, then the node itself, then the right subtree) and print out the key of each node. You can implement this method using a recursive helper function called inorderRec. This helper function should take in the current root node and traverse the left subtree, the root node itself, and the right subtree recursively.
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
5. Create an instance of the BinaryTree class and insert elements in the tree by calling
BinaryTree tree = new BinaryTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
Implementation of Binary Data Structure in Java :
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() {
root = null;
}
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
}
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment