Question of the Week #162
How can one implement a binary tree in Java?
#Week 162 — How can one implement a binary tree in Java?
modest jasperBOT
pulsar pathBOT
Binary trees are a data structure consisting of nodes having up to two children each. At the top of the tree, there is a root node without any parents.
public class Node<T> {
private Node<T> left;
private Node<T> right;
private T data;
public Node(T data) {
this.data = data;
}
public Node<T> getLeft() {
return left;
}
public Node<T> getRight() {
return right;
}
public T getData() {
return data;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public void setRight(Node<T> right) {
this.right = right;
}
public void setData(T data) {
this.data = data;
}
}
public class BinaryTree<T> {
private Node<T> root;
public BinaryTree(Node<T> root){
this.root = root;
}
public Node<T> getRoot(){
return root;
}
public void setRoot(Node<T> root) {
this.root = root;
}
}
As a binary tree is a tree, it must not have cycles i.e. the same node must not be present multiple times in a (binary) tree.
Binary trees can be traversed in-order (first the left node, then the parent, then the right node), depth-first (first the left and right node, then the parent) or breadth-first (first the parent, then the left and right node):
public <T> void printDataInOrder(BinaryTree<T> tree) {
printDataInOrder(tree.getRoot());
}
private <T> void printDataInOrder(Node<T> node) {
if (node == null) {
return;
}
printDataInOrder(node.getLeft());
System.out.println(node.getData());
printDataInOrder(node.getRight());
}
public <T> void printDataDepthFirst(BinaryTree<T> tree) {
printDataDepthFirst(tree.getRoot());
}
private <T> void printDataDepthFirst(Node<T> node) {
if (node == null) {
return;
}
printDataDepthFirst(node.getLeft());
printDataDepthFirst(node.getRight());
System.out.println(node.getData());
}
public <T> void printDataBreadthFirst(BinaryTree<T> tree) {
printDataBreadthFirst(tree.getRoot());
}
private <T> void printDataBreadthFirst(Node<T> node) {
if (node == null) {
return;
}
System.out.println(node.getData());
printDataBreadthFirst(node.getLeft());
printDataBreadthFirst(node.getRight());
}
A binary search tree (BST) is a special binary tree where the nodes are always sorted when traversing the tree in-order. That allows for quickly searching for nodes in a binary search tree.
public class BinarySearchTree<T extends Comparable<T>> {
private Node<T> root;
public void insert(T data) {
Objects.requireNonNull(data);
if (root == null) {
root = new Node<>(data);
} else {
insert(root, new Node<>(data));
}
}
private void insert(Node<T> current, Node<T> toInsert) {
int cmp = toInsert.getData().compareTo(current.getData());
if (cmp < 0) { // data < current
if (current.getLeft() == null) {
current.setLeft(toInsert);
} else {
insert(current.getLeft(), toInsert);
}
} else if(cmp > 0) { // data > current
if (current.getRight() == null) {
current.setRight(toInsert);
} else {
insert(current.getRight(), toInsert);
}
} else {
// value already inserted
// do nothing (alternatively one could insert it on either side or throw an exception)
}
}
public boolean contains(T data) {
return contains(root, Objects.requireNonNull(data));
}
private boolean contains(Node<T> current, T data) {
if (current == null) {
return false;
}
int cmp = data.compareTo(current.getData());
if (cmp < 0) { // data < current
return contains(current.getLeft(), data);
} else if (cmp > 0) { // data > current
return contains(current.getRight(), data);
} else {
return true;
}
}
public <T> void printElements() {
printElements(root);
}
private <T> void printElements(Node<T> node) {
if (node == null) {
return;
}
printElements(node.getLeft());
System.out.println(node.getData());
printElements(node.getRight());
}
}
To add capabilities for removing elements to the binary search tree, a method similar to the following can be added to the class:
public void remove(T data) {
if (root == null) {
return;
}
root = remove(root, Objects.requireNonNull(data));
}
private Node<T> remove(Node<T> current, T data) {
int cmp = data.compareTo(current.getData());
if (cmp < 0) { // data < current
if (current.getLeft() != null) {
current.setLeft(remove(current.getLeft(), data));
} // else not found
} else if (cmp > 0) { // data > current
if (current.getRight() != null) {
current.setRight(remove(current.getRight(), data));
}//else not found
} else if(current.getLeft() == null) {
return current.getRight();
} else if(current.getRight() == null) {
return current.getLeft();
} else {
insert(current.getLeft(), current.getRight());
return current.getLeft();
}
return current;
}
Maintaining binary search trees like that can result in them becoming unbalanced (some branches being very deep while others aren't) making the search slower than it would be with a balanced BST (where all leaf nodes have (roughly) the same depth). In the worse case, a binary search tree can "degenerate" into a linked list meaning that each node only has a single child and searching can require checking all elements until the correct one is found.
To prevent that from happening, certain types of (binary) search trees like AVL- or red/black trees ensure that they are always balanced. These types of trees are called self-balancing.
📖 Sample answer from dan1st
This is how we can implement Binary Tree in Java :
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() {
root = null;
}
}
public class Main {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
}
}
Submission from rajveer6085
Binary three is made of Nodes, node has three things data and two child nodes
public class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
public Node() {
data = 0;
}
}
Using this Node structure Binary Tree can be implemented.