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 binary tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child. The path is called a path from the root to the leftmost child, and from the leftmost child to the rightmost child.

**A binary tree has the following properties: **

- Each node has at most two children
- The left child of a node is less than the right child of a node
- The right child of a node is greater than the left child of a node
- A node is a leaf node if it has no children

**Examples of coding problems using trees:**

**What is the difference between a binary tree and a binary search tree?**

A binary tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child. The path is called a path from the root to the leftmost child, and from the leftmost child to the rightmost child.

A binary search tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child, such that the left child is less than the right child.

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

- Binary search trees support many dynamic-set operations, including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT and DELETE.
- Basic operations on a binary search tree take time proportional to the height of the tree – which is O(lg n) for a complete binary tree with n nodes.
- In practice, we can’t always guarantee that binary search trees are built randomly – but there are variations (like red-black trees) with good guaranteed worst-case performance on basic operations.
- After presenting the basic properties of binary search trees, the following sections show how to walk a binary search tree to print its values in sorted order; how to find a value in a binary search; minimum or maximum element; predecessor or successor of an element; insert into or delete from a binary search tree.

We can represent a tree node using class. Below is an example of a tree node with integer data.

class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } }

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

## What are the Types of Binary Trees?

The three types of binary trees are full, complete, and perfect.

A *full *binary tree is a binary tree in which every node has either zero or two children. A full binary tree is also sometimes called a proper or strict binary tree.

A *complete *binary tree is a binary tree in which every level of the tree is fully filled, except for possibly the last level. The last level of a complete binary tree is filled from left to right. explain a perfect binary tree A perfect binary tree is a binary tree in which all of the leaves are at the same level, and all of the internal nodes have two children.

A *perfect *binary tree is a binary tree in which all of the leaves are at the same level, and all of the internal nodes have two children.

## Implementing a binary tree.

We will use an auxiliary Node class to store int values and keep references to each child. The first step is to find the place where we want to add the new node in order to keep the tree sorted. To do this, we will follow these rules starting from the root node:

– If the value to be added is smaller than the root value, we will go to the left subtree.

– If the value to be added is larger than the root value, we will go to the right subtree.

– If we reach a leaf node, it means we have found the place to add the new node.

Let’s do the implementation in **JavaScript** we will use functional programming first:

function BinarySearchTree() { var root = null; this.insert = function(value){ if (root === null){ root = new Node(value); } else { insertNode(root, value); } } this.remove = function(value){ root = removeNode(root, value); } this.search = function(value){ return searchNode(root, value); } this.inorder = function(){ inorderTraverseNode(root); } this.preorder = function(){ preorderTraverseNode(root); } this.postorder = function(){ postorderTraverseNode(root); } this.min = function(){ return minNode(root); } this.max = function(){ return maxNode(root); } } function insertNode(node, newVal) { if (newVal < node.value) { if (node.left === null) { node.left = new Node(newVal); } else { insertNode(node.left, newVal); } } else { if (node.right === null) { node.right = new Node(newVal); } else { insertNode(node.right, newVal); } } } function removeNode(node, key) { if (node === null) { return null; } if (key < node.value) { node.left = removeNode(node.left, key); return node; } else if (key > node.value) { node.right = removeNode(node.right, key); return node; } else { if (node.left === null && node.right === null) { node = null; return node; } if (node.left === null) { node = node.right; return node; } else if (node.right === null) { node = node.left; return node; } var aux = minNode(node.right); node.value = aux.value; node.right = removeNode(node.right, aux.value); return node; } } function searchNode(node, key) { if (node === null) { return false; } if (key < node.value) { return searchNode(node.left, key); } else if (key > node.value) { return searchNode(node.right, key); } else { return true; } } function inorderTraverseNode(node) { if (node !== null) { inorderTraverseNode(node.left); console.log(node.value); inorderTraverseNode(node.right); } } function preorderTraverseNode(node) { if (node !== null) { console.log(node.value); preorderTraverseNode(node.left); preorderTraverseNode(node.right); } } function postorderTraverseNode(node) { if (node !== null) { postorderTraverseNode(node.left); postorderTraverseNode(node.right); console.log(node.value); } } function minNode(node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.value; } return null; } function maxNode(node) { if (node) { while (node && node.right !== null) { node = node.right; } return node.value; } return null; }

Using JavaScript Class

class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinaryTree { constructor() { this.root = null; } // function to insert a node in the tree insert(value) { const newNode = new Node(value); // if the tree is empty, set the root to the new node if (this.root === null) { this.root = newNode; } else { // find the correct position in the tree and insert the new node this.insertNode(this.root, newNode); } } // helper function to insert a node in the correct position in the tree insertNode(node, newNode) { // if the value of the new node is less than the value of the current node, insert it in the left subtree if (newNode.value < node.value) { // if the left child of the current node is null, set the left child to the new node if (node.left === null) { node.left = newNode; } else { // if the left child is not null, recurse through the left subtree this.insertNode(node.left, newNode); } } else { // if the value of the new node is greater than or equal to the value of the current node, insert it in the right subtree if (node.right === null) { node.right = newNode; } else { // if the right child is not null, recurse through the right subtree this.insertNode(node.right, newNode); } } } // function to remove a node from the tree remove(value) { // if the tree is empty, return null if (this.root === null) { return null; } else { // find the node to be removed and remove it this.root = this.removeNode(this.root, value); } } // helper function to remove a node from the tree removeNode(node, value) { // if the tree is empty, return null if (node === null) { return null; } // if the value to be removed is less than the value of the current node, recurse through the left subtree if (value < node.value) { node.left = this.removeNode(node.left, value); return node; } else if (value > node.value) { // if the value to be removed is greater than the value of the current node, recurse through the right subtree node.right = this.removeNode(node.right, value); return node; } else { // if the value to be removed is equal to the value of the current node, remove the node // if the node to be removed has no children, set it to null if (node.left === null && node.right === null) { node = null; return node; } // if the node to be removed has no left child, set the node to its right child if (node.left === null) { node = node.right; return node; } else if (node.right === null) { // if the node to be removed has no right child, set the node to its left child node = node.left; return node; } // if the node to be removed has two children, find the minimum value in the right subtree const minValue = this.findMinValue(node.right); node.value = minValue; // remove the minimum value from the right subtree node.right = this.removeNode(node.right, minValue); return node; } } // function to find the minimum value in a subtree findMinValue(node) { if (node.left === null) { return node.value; } else { return this.findMinValue(node.left); } } // function to search for a value in the tree search(value) { // if the tree is empty, return false if (this.root === null) { return false; } else { // search for the value in the tree return this.searchNode(this.root, value); } } // helper function to search for a value in the tree searchNode(node, value) { // if the tree is empty, return false if (node === null) { return false; } // if the value is less than the value of the current node, recurse through the left subtree if (value < node.value) { return this.searchNode(node.left, value); } else if (value > node.value) { // if the value is greater than the value of the current node, recurse through the right subtree return this.searchNode(node.right, value); } else { // if the value is equal to the value of the current node, return true return true; } } }