Types of Binary Tree
Binary trees can be classified into several types based on their structure and properties:
- Full Binary Tree: A full binary tree is a binary tree in which every node other than the leaves has exactly two children. All leaves are at the same level.
- Complete Binary Tree: A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
- Perfect Binary Tree: A perfect binary tree is a binary tree in which all internal nodes have exactly two children, and all leaf nodes are at the same level.
- Balanced Binary Tree: A balanced binary tree is a binary tree in which the height of the left and right subtrees of any node differ by at most one.
- Degenerate (or Pathological) Binary Tree: A degenerate binary tree is a binary tree in which each parent node has only one associated child node.
Binary Tree Implementation in Java
Binary trees can be implemented in Java using different methods, including:
Node Class Implementation
- Define a class representing a node in the binary tree.
- Each node contains data and references to its left and right children.
- Use recursive methods for operations like insertion, deletion, and traversal.
Java
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
// Constructor
BinaryTree() {
root = null;
}
// Insertion method
void insert(int data) {
root = insertRec(root, data);
}
Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
return root;
}
// Inorder traversal method
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// Inserting elements
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Printing inorder traversal
tree.inorder();
}
}
You can also try this code with Online Java Compiler
Output:
20 30 40 50 60 70 80
Using Arrays
- Represent the binary tree using an array.
- For a node at index i, its left child is at index 2*i+1 and the right child is at index 2*i+2.
- This method is useful for complete binary trees but can be inefficient for sparse trees.
Java
class BinaryTree {
static int[] arr = new int[10];
static int count = 0;
// Insertion method
static void insert(int data) {
arr[count++] = data;
}
// Inorder traversal method
static void inorder(int index) {
if (index < count) {
inorder(2 * index + 1);
System.out.print(arr[index] + " ");
inorder(2 * index + 2);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// Inserting elements
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Printing inorder traversal
tree.inorder(0);
}
}
You can also try this code with Online Java Compiler
Output:
20 30 40 50 60 70 80
Using Linked List Representation
- Create a class representing the binary tree.
- Each node in the tree is represented as an object with references to its left and right children.
- Use recursive methods for tree operations.
Java
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
// Constructor
BinaryTree() {
root = null;
}
// Insertion method
void insert(int data) {
root = insertRec(root, data);
}
Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
return root;
}
// Inorder traversal method
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// Inserting elements
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Printing inorder traversal
tree.inorder();
}
}
You can also try this code with Online Java Compiler
Output:
20 30 40 50 60 70 80
Using Queue for Level Order Traversal
- Implement a level order traversal using a queue.
- Enqueue the root node, and then dequeue and enqueue its children sequentially.
- Repeat this process until all nodes are traversed.
Java
import java.util.LinkedList;
import java.util.Queue;
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
// Constructor
BinaryTree() {
root = null;
}
// Insertion method
void insert(int data) {
root = insertRec(root, data);
}
Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
return root;
}
// Level order traversal method
void levelOrder() {
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
if (tempNode.left != null)
queue.add(tempNode.left);
if (tempNode.right != null)
queue.add(tempNode.right);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// Inserting elements
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// Printing level order traversal
tree.levelOrder();
}
}
You can also try this code with Online Java Compiler
Output:
50 30 70 20 40 60 80
Binary Tree Operations
Inserting Elements
- First, locate the place where we need to insert the node.
- Traverse to the left child if the new node's value is lower than the current node's value.
- Traverse to the right child if the new node's value is greater than the current node's value.
- If the current node is null, we've reached a leaf node and hence we can insert the new node in that position. Then we can follow a recursive method for insertion.
private Node Recursive_Addition(Node curr_node, int val) {
if (curr_node == null) {
return new Node(val);
}
else if (val < curr_node.val) {
curr_node.left = Recursive_Addition(curr_node.left, val);
} else if (val > curr_node.val) {
curr_node.right = Recursive_Addition(curr_node.right, val);
} else {
// val already exists
return curr_node;
}
return curr_node;
}
public void add(int val) {
root = Recursive_Addition(root, val);
}
Finding an Element
- Create a recursive method that traverses the tree.
- Search for the value by comparing it to the value of the current node and then continue left or right depending upon the outcome.
private boolean find_node(Node current_node, int val) {
if (current_node == null) {
return false;
}
if (val == current_node.val) {
return true;
}
return val < current_node.val
? find_node(current_node.left, val)
: find_node(current_node.right, val);
}
public boolean containsNode(int val) {
return find_node(root, val);
}
Deleting an Element
First, find the node to be deleted similarly as before. Once the node is found, there are 3 prominent different cases:
- A node has no children: Need to replace this node with null in its parent node.
- A node has one child: In the parent node, we replace this node with its only child.
- A node has two children: Requires a tree reorganization.
private Node delete_recursive(Node current_node, int val) {
if (current_node == null) {
return null;
}
if (val == current_node.val) {
// ... deletion code
}
if (val < current_node.val) {
current_node.left = delete_recursive(current_node.left, val);
return current_node;
}
current_node.right = delete_recursive(current_node.right, val);
return current_node;
}
if (current_node.left == null && current_node.right == null) {
return null;
}
// If node has one child:
if (current_node.right == null) {
return current_node.left;
}
if (current_node.left == null) {
return current_node.right;
}
private int smallest_value(Node root) {
return root.left == null ? root.val : smallest_value(root.left);
}
int smallestValue = smallest_value(current_node.right);
current_node.val = smallestValue;
current_node.right = delete_recursive(current_node.right, smallestValue);
return current_node;
public void delete(int val) {
root = delete_recursive(root, val);
}
Depth-First Search
It is a type of traversal that goes deep into a node as possible in every child and then explores the next sibling of the currently visited node.
Ways to perform a depth-first search: -
Inorder - the left subtree, then the root node, and finally the right sub-tree.
public void InOrder(Node node) {
if (node != null) {
InOrder(node.left);
System.out.print(" " + node.value);
InOrder(node.right);
}
}
Pre-Order - the root node, then the left sub-tree, and finally the right sub-tree.
public void PreOrder(Node node) {
if (node != null) {
System.out.print(" " + node.value);
PreOrder(node.left);
PreOrder(node.right);
}
}
Post-Order - the left subtree, then the right sub-tree, and finally the root node
public void PostOrder(Node node) {
if (node != null) {
PostOrder(node.left);
PostOrder(node.right);
System.out.print(" " + node.value);
}
}
Breadth-First Search
In this traversal, the pointer visits all the nodes of a level before going to the next level. We use the queue data structure for implementation.
public void traverseLevelOrder() {
if (root == null)
return;
Queue<Node> nodes = new List<>();
nodes.add_node(root);
while (!nodes.isEmpty()) {
Node node = nodes.remove();
System.out.print(" " + node.value);
if (node.left != null)
nodes.add_node(node.left);
if (node.right != null)
nodes.add_node(node.right);
}
}
Frequently Asked Questions
How to code a tree in Java?
To code a tree in Java, define a class for the tree node with data and references to left and right children. Implement methods for insertion, deletion, and traversal. Use recursion for tree operations.
What is binary tree example?
An example of a binary tree is a family tree, where each person (node) has at most two children (parents). Each node represents a person, and the left child is typically the father, while the right child is the mother.
What is a binary tree in Java?
A binary tree in Java is a hierarchical data structure composed of nodes, where each node has at most two children. It represents a tree-like structure with a single root node and branches downward to form subtrees.
How to create a binary tree?
To create a binary tree in Java, define a class for the tree node with data and references to left and right children. Use insertion methods to add nodes to the tree, ensuring that each node is placed correctly according to its value.
Conclusion
In this article, we have extensively discussed Implementing a Binary Tree in Java. Understanding and implementing a binary tree in Java is essential for mastering data structures and algorithms. With the provided insights and examples, you can now confidently create, manipulate, and traverse binary trees.
Recommended problems -
19+ registered 
