Trees in Java — How to Implement a Binary Tree?

Trees in Java — How to Implement a Binary Tree?

Image for postTrees in Java ? Edureka

If I had to pick the single most important topic in software development, it would be data structures. One of the most common and easiest ones is a tree ? a hierarchical data structure. In this article, let?s explore Trees in Java.

  • What is a Binary Tree?
  • Types of Binary Tree
  • Binary Tree Implementation
  • Tree Traversals
  • Applications of Binary Tree

What is a Binary Tree?

A is a non-linear data structure where data objects are generally organized in terms of hierarchical relationship. The structure is non-linear in the sense that, unlike Arrays, Linked Lists, Stack and Queues, data in a tree is not organized linearly. A binary tree is a recursive tree data structure where each node can have 2 children at most.

Image for post

Binary trees have a few interesting properties when they?re perfect:

  • Property 1: The number of total nodes on each ?level? doubles as you move down the tree.
  • Property 2: The number of nodes on the last level is equal to the sum of the number of nodes on all other levels, plus 1

Each data element stored in a tree structure called a node. A Tree node contains the following parts: 1. Data

2. Pointer to left child

3. Pointer to the right child

In Java, we can represent a tree node using class. Below is an example of a tree node with integer data.

static class Node { int value; Node left, right; Node(int value){ this.value = value; left = null; right = null; }

Now that you know what is a binary tree, let?s check out different types of binary trees.

Types of Binary Trees

Full Binary Tree

A full binary tree is a binary tree where every node has exactly 0 or 2 children. The example of fully binary tress is:

Image for post

Perfect Binary Tree

A binary tree is perfect binary Tree if all internal nodes have two children and all leaves are at the same level. The example of perfect binary tress is:

Image for post

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. An example of a complete binary tree is:

Image for post

Now that you are aware of different types of binary trees, let?s check out how to create a binary tree.

Binary Tree Implementation

For the implementation, there?s an auxiliary Node class that will store int values and keeps a reference to each child. The first step is to find the place where we want to add a new node in order to keep the tree sorted. We?ll follow these rules starting from the root node:

  • if the new node?s value is lower than the current node?s, go to the left child
  • if the new node?s value is greater than the current node?s, go to the right child
  • when the current node is null, we?ve reached a leaf node, we insert the new node in that position

Now let?s see how we can implement this logic with the help of an example:

package MyPackage; public class Tree { static class Node { int value; Node left, right; Node(int value){ this.value = value; left = null; right = null; } } public void insert(Node node, int value) { if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { System.out.println(” Inserted ” + value + ” to left of ” + node.value); node.left = new Node(value); } } else if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(” Inserted ” + value + ” to right of ” + node.value); node.right = new Node(value); } } } public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(” ” + node.value); traverseInOrder(node.right); } } public static void main(String args) { Tree tree = new Tree(); Node root = new Node(5); System.out.println(“Binary Tree Example”); System.out.println(“Building tree with root value ” + root.value); tree.insert(root, 2); tree.insert(root, 4); tree.insert(root, 8); tree.insert(root, 6); tree.insert(root, 7); tree.insert(root, 3); tree.insert(root, 9); System.out.println(“Traversing tree in order”); tree.traverseLevelOrder(); }}

Output:

Binary Tree ExampleBuilding tree with root value 5 Inserted 2 to left of 5 Inserted 4 to right of 2 Inserted 8 to right of 5 Inserted 6 to left of 8 Inserted 7 to right of 6 Inserted 3 to left of 4 Inserted 9 to right of 8Traversing tree in order 2 3 4 5 6 7 8 9

In this example, we have used in-order traversal to traverse the tree. The in-order traversal consists of first visiting the left sub-tree, then the root node, and finally the right sub-tree. There are more ways to traverse a tree. Let?s check them out.

Tree Traversals

Trees can be traversed in several ways: Let?s use the same tree example that we used before for each case.

Depth First Search

Depth-first search is a type of traversal where you go as deep as possible down one path before backing up and trying a different one. There are several ways to perform a depth-first search: in-order, pre-order and post-order.

We already checked out in-order traversal. Let?s check out pre-order and post-order now.

Pre-Order Traversal

In Pre-order traversal you visit the root node first, then the left subtree, and finally the right subtree. Here?s the code.

public void traversePreOrder(Node node) { if (node != null) { System.out.print(” ” + node.value); traversePreOrder(node.left); traversePreOrder(node.right); }}

Output:

5 2 4 3 8 6 7 9

Post-Order Traversal

In Post-order traversal you visit left subtree first, then the right subtree, and the root node at the end. Here?s the code.

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(” ” + node.value); }}

Output:

3 4 2 7 6 9 8 5

Breadth-First Search

This type of traversal visits all the nodes of a level before going to the next level. It is like throwing a stone in the center of a pond. The nodes you explore ?ripple out? from the starting point. Breadth-First Search is also called level-order and visits all the levels of the tree starting from the root, and from left to right.

Applications of Binary Tree

Applications of binary trees include:

  • Used in many search applications where data is constantly entering/leaving
  • As a workflow for compositing digital images for visual effects
  • Used in almost every high-bandwidth router for storing router-tables
  • Also used in wireless networking and memory allocation
  • Used in compression algorithms and many more

This brings us to the end of this ?Trees in Java? article.

Make sure you practice as much as possible and revert your experience.

If you wish to check out more articles on the market?s most trending technologies like Artificial Intelligence, DevOps, Ethical Hacking, then you can refer to Edureka?s official site.

Do look out for other articles in this series which will explain the various other aspects of Java.

1. Object Oriented Programming

2. Inheritance in Java

3. Polymorphism in Java

4. Abstraction in Java

5. Java String

6. Java Array

7. Java Collections

8. Java Threads

9. Introduction to Java Servlets

10. Servlet and JSP Tutorial

11. Exception Handling in Java

12. Advanced Java Tutorial

13. Java Interview Questions

14. Java Programs

15. Kotlin vs Java

16. Dependency Injection Using Spring Boot

17. Comparable in Java

18. Top 10 Java frameworks

19. Java Reflection API

20. Top 30 Patterns in Java

21. Core Java Cheat Sheet

22. Socket Programming In Java

23. Java OOP Cheat Sheet

24. Annotations in Java

25. Library Management System Project in Java

26. Java Tutorial

27. Machine Learning in Java

28. Top Data Structures & Algorithms in Java

29. Java Developer Skills

30. Top 55 Servlet Interview Questions

31. Top Java Projects

32. Java Strings Cheat Sheet

33. Nested Class in Java

34. Java Collections Interview Questions and Answers

35. How to Handle Deadlock in Java?

36. Top 50 Java Collections Interview Questions You Need to Know

37. What is the concept of String Pool in Java?

38. What is the difference between C, C++, and Java?

39. Palindrome in Java- How to check a number or string?

40. Top MVC Interview Questions and Answers You Need to Know

41. Top 10 Applications of Java Programming Language

Originally published at https://www.edureka.co on September 3, 2019.

11

No Responses

Write a response