Trees in Java

Trees are an important data structure that is found in many computer science applications. They are used to store and organize data in a hierarchical structure. Trees are composed of nodes, each of which can have multiple children and a single parent.

Trees are used for many purposes, including sorting, searching, and data retrieval. In this article, we will discuss the fundamentals of trees, how to implement trees using classes in Java, and how to traverse, insert, and delete elements from a tree.

Overview of Trees

Trees are a type of data structure that is composed of nodes that are connected in a hierarchical fashion. They are usually represented as a diagram that looks like an upside-down tree, with the root at the top and the leaves at the bottom.

Each node in a tree can have multiple children and a single parent. The root node is the node at the top of the tree, and it has no parent. The leaves are the nodes at the bottom of the tree and have no children.

The main purpose of a tree is to store and organize data in a hierarchical manner. Trees can be used for all sorts of applications, such as sorting, searching, and data retrieval.

Implementing Trees Using Classes in Java

Now that we have an understanding of what trees are and why they are used, let’s look at how to implement a tree using classes in Java.

The first thing we need to do is create a Node class. This will be used to represent each node in our tree.

public class Node { 
  int data; 
  Node left; 
  Node right; 
 
  public Node(int data) { 
    this.data = data; 
    this.left = null; 
    this.right = null; 
  } 
}

The Node class has three fields: data, left, and right. The data field is used to store the data associated with the node, and the left and right fields are used to store references to the left and right children of the node.

Now that we have our Node class, we can create a Tree class. This will be used to represent the entire tree.

public class Tree { 
  Node root; 
 
  public Tree() { 
    this.root = null; 
  } 
}

The Tree class has one field: root. This is used to store a reference to the root node of the tree.

Traversing a Tree

Now that we have our Node and Tree classes, let’s look at how to traverse a tree. Traversing a tree means moving through the tree and visiting each node.

The most common way to traverse a tree is called in-order traversal. In-order traversal starts at the root node and visits the left child, then the current node, then the right child. This process is repeated until all the nodes in the tree have been visited.

Here is a Java method that implements in-order traversal:

public void inOrder(Node node) { 
  if (node != null) { 
    inOrder(node.left); 
    System.out.print(node.data + " "); 
    inOrder(node.right); 
  } 
}

This method takes a node as a parameter and recursively visits the left child, then prints the data associated with the node, and then visits the right child.

Inserting and Deleting Elements from a Tree

Now that we know how to traverse a tree, let’s look at how to insert and delete elements from a tree.

Inserting an element into a tree is as simple as creating a new node and adding it to the tree. Here is a Java method that implements this:

public void insert(int data) { 
  Node newNode = new Node(data); 
 
  if (root == null) { 
    root = newNode; 
  } else { 
    Node current = root; 
    Node parent; 
    while (true) { 
      parent = current; 
      if (data < current.data) { 
        current = current.left; 
        if (current == null) { 
          parent.left = newNode; 
          return; 
        } 
      } else { 
        current = current.right; 
        if (current == null) { 
          parent.right = newNode; 
          return; 
        } 
      } 
    } 
  } 
} 

This method takes a value as a parameter and creates a new node with that value. It then traverses the tree to find the appropriate place to insert the new node.

Deleting an element from a tree is slightly more complicated. First, we need to find the node that we want to delete, and then we need to adjust the links in the tree to ensure that all the nodes are still connected properly.

Here is a Java method that implements deleting a node from a tree:

public boolean delete(int data) { 
  Node current = root; 
  Node parent = root; 
  boolean isLeftChild = false; 
 
  // Find the node to be deleted 
  while (current.data != data) { 
    parent = current; 
    if (data < current.data) { 
      isLeftChild = true; 
      current = current.left; 
    } else { 
      isLeftChild = false; 
      current = current.right; 
    } 
 
    if (current == null) { 
      return false; 
    } 
  } 
 
  // Case 1: if the node to be deleted has no children 
  if (current.left == null && current.right == null) { 
    if (current == root) { 
      root = null; 
    } else if (isLeftChild) { 
      parent.left = null; 
    } else { 
      parent.right = null; 
    } 
  } 
 
  // Case 2: if the node to be deleted has one child 
  else if (current.right == null) { 
    if (current == root) { 
      root = current.left; 
    } else if (isLeftChild) { 
      parent.left = current.left; 
    } else { 
      parent.right = current.left; 
    } 
  } 
  else if (current.left == null) { 
    if (current == root) { 
      root = current.right; 
    } else if (isLeftChild) { 
      parent.left = current.right; 
    } else { 
      parent.right = current.right; 
    } 
  } 
 
  // Case 3: if the node to be deleted has two children 
  else if (current.left != null && current.right != null) { 
    Node successor = getSuccessor(current); 
 
    // Connect the parent of the current node to the successor node 
    if (current == root) { 
      root = successor; 
    } else if (isLeftChild) { 
      parent.left = successor; 
    } else { 
      parent.right = successor; 
    } 
 
    successor.left = current.left; 
  } 
  return true; 
} 

This method takes a value as a parameter and traverses the tree to find the node with that value. If it finds the node, it deletes it and adjusts the links in the tree accordingly.

Conclusion

In this article, we discussed the fundamentals of trees, how to implement trees using classes in Java, and how to traverse, insert, and delete elements from a tree. Trees are an important data structure that is used for sorting, searching, and data retrieval. We saw how to create a Node and Tree class in Java and how to traverse, insert, and delete elements from a tree.

Exercises

public void preOrder(Node node) { 
  if (node != null) { 
    System.out.print(node.data + " "); 
    preOrder(node.left); 
    preOrder(node.right); 
  } 
}

public void insertBST(int data) { 
  Node newNode = new Node(data); 
 
  if (root == null) { 
    root = newNode; 
  } else { 
    Node current = root; 
    Node parent; 
    while (true) { 
      parent = current; 
      if (data < current.data) { 
        current = current.left; 
        if (current == null) { 
          parent.left = newNode; 
          return; 
        } 
      } else { 
        current = current.right; 
        if (current == null) { 
          parent.right = newNode; 
          return; 
        } 
      } 
    } 
  } 
} 

public boolean deleteBST(int data) { 
  Node current = root; 
  Node parent = root; 
  boolean isLeftChild = false; 
 
  // Find the node to be deleted 
  while (current.data != data) { 
    parent = current; 
    if (data < current.data) { 
      isLeftChild = true; 
      current = current.left; 
    } else { 
      isLeftChild = false; 
      current = current.right; 
    } 
 
    if (current == null) { 
      return false; 
    } 
  } 
 
  // Case 1: if the node to be deleted has no children 
  if (current.left == null && current.right == null) { 
    if (current == root) { 
      root = null; 
    } else if (isLeftChild) { 
      parent.left = null; 
    } else { 
      parent.right = null; 
    } 
  } 
 
  // Case 2: if the node to be deleted has one child 
  else if (current.right == null) { 
    if (current == root) { 
      root = current.left; 
    } else if (isLeftChild) { 
      parent.left = current.left; 
    } else { 
      parent.right = current.left; 
    } 
  } 
  else if (current.left == null) { 
    if (current == root) { 
      root = current.right; 
    } else if (isLeftChild) { 
      parent.left = current.right; 
    } else { 
      parent.right = current.right; 
    } 
  } 
 
  // Case 3: if the node to be deleted has two children 
  else if (current.left != null && current.right != null) { 
    Node successor = getSuccessor(current); 
 
    // Connect the parent of the current node to the successor node 
    if (current == root) { 
      root = successor; 
    } else if (isLeftChild) { 
      parent.left = successor; 
    } else { 
      parent.right = successor; 
    } 
 
    successor.left = current.left; 
  } 
  return true; 
} 

public Node search(int data) { 
  Node current = root; 
 
  while (current != null) { 
    if (current.data == data) { 
      return current; 
    } else if (data < current.data) { 
      current = current.left; 
    } else { 
      current = current.right; 
    } 
  } 
 
  return null; 
} 

public int countNodes(Node node) { 
  int count = 0; 
 
  if (node != null) { 
    count++; 
    count += countNodes(node.left); 
    count += countNodes(node.right); 
  } 
 
  return count; 
}