A Binary Tree is a tree data structure where each node has no more than two child nodes, known as the left child and right child. If every node in a tree can have at most two children, the tree is called a binary tree.

Components of a Binary Tree

1. Root – The node at the top of the tree is called the root. There is only one root in a tree. For a collection of nodes and edges to be defined as a tree, there must be one path from the root to any other node.
2. Path – walking from node to node along the edges that connect them. The resulting sequence of nodes is called a path.
3. Parent Node – Any node has exactly one edge running upward to another node. The node above it is called the parent of the node.
4. Child Node – Any node may have one or more lines running downward to other nodes. These nodes below a given node are called its children.
5. Leaf Node – A node that has no children is called a leaf node or simply a leaf. There can be only one root in a tree, but there can be many leaves.
6. Subtree – Any node may be considered to be the root of a subtree, which consists of its children, and its children’s children, and so on. If you think in terms of families, a node’s subtree contains all its descendants.
7. Traversing – To traverse a tree means to visit all the nodes in some specified order.

How to insert new node in Tree

Step-by-Step Logic of Insertion

1. Start from the root node.
2. Compare the new value with the current node value.
3. If the new value is less than the current node, move to the left child.
4. If the new value is greater than the current node, move to the right child.
5. Repeat this process until a NULL position is found.
6. Insert the new node at that position.

1. Node.java

package com.test.rkdigital.school.tree;
public class Node {
	public int iData; // data item (key)
	public double dData; // data item
	public Node leftChild; // this node’s left child
	public Node rightChild; // this node’s right child
}

2.RkdigitalTree.java

package com.test.rkdigital.school.tree;

public class RkdigitalTree 
{
	private Node root;

	public RkdigitalTree(){
		root=null;
	}

	public void insert(int id, double dd)
	{
		//Create new node
		Node newNode = new Node(); 
		newNode.iData = id; 
		newNode.dData = dd;
		
		// no node in root
		if(root==null)
			root = newNode;
		else 
		{
			Node current = root; // start at root
			Node parent;
			while(true) // (exits internally)
			{
				parent = current;
				if(id < current.iData) // go left?
				{
				current = current.leftChild;
				if(current == null) 
				{
				// insert on left
				parent.leftChild = newNode;
				return;
			}
			} 
			else 
			{
			  current = current.rightChild;
			  // if end of the line
			  if(current == null) 
			  { 
			    // insert on right
			    parent.rightChild = newNode;
			    return;
			}
		} 
	    } 
	} 
	}

	public static void main(String[] args) {

		RkdigitalTree rkTree = new RkdigitalTree();
		rkTree.insert(10, 1.5);
		rkTree.insert(25, 1.2);
		rkTree.insert(75, 1.7);
		rkTree.insert(12, 1.5);
		rkTree.insert(37, 1.2);
		rkTree.insert(13, 1.7);
		rkTree.insert(30, 1.5);
		rkTree.insert(33, 1.2);
		rkTree.insert(77, 1.7);
		rkTree.insert(93, 1.5);
		rkTree.insert(97, 1.5);
	}
}

How to find a node in tree

Finding a node in a Binary Tree is the process of searching for a particular element in the tree structure. The search starts from the root node and moves through the left subtree and right subtree until the required value is found.

package com.test.rkdigital.school.tree;

public class RkdigitalTree 
{
	private Node root;
	public RkdigitalTree(){
		root=null;
	}
	public void insert(int id, double dd)
	{
		//Create new node
		Node newNode = new Node(); 
		newNode.iData = id; 
		newNode.dData = dd;
		// no node in root
		if(root==null)
			root = newNode;
		else 
		{
			Node current = root; // start at root
			Node parent;
			//(exits internally)
			while(true) 
			{
			parent = current;
			if(id < current.iData) // go left?
				{
				current = current.leftChild;
				if(current == null) 
				{
				 // insert on left
				 parent.leftChild = newNode;
				 return;
			}
		} 
		else 
		{
		  current = current.rightChild;
		  // if end of the line
		  if(current == null) 
		  { 
		    // insert on right
		    parent.rightChild = newNode;
		    return;
		   }
		} 
	      } 
	   } 
	}

	// find node with given key
	public Node find(int key) 
	{ 
		//start at root
		Node current = root; 
		// while no match,
		while(current.iData != key) 
		{
			if(key < current.iData) // go left?
				current = current.leftChild;
			else // or go right?
				current = current.rightChild;
			if(current == null) // if no child,
				return null; // didn’t find it
		}
		return current; // found it
	}
	
	public static void main(String[] args) {

		RkdigitalTree rkTree = new RkdigitalTree();
		rkTree.insert(10, 1.5);
		rkTree.insert(25, 1.2);
		rkTree.insert(75, 1.7);
		rkTree.insert(12, 1.5);
		rkTree.insert(37, 1.2);
		rkTree.insert(13, 1.7);
		rkTree.insert(30, 1.5);
		rkTree.insert(33, 1.2);
		rkTree.insert(77, 1.7);
		rkTree.insert(93, 1.5);
		rkTree.insert(97, 1.5);
		
		Node node=rkTree.find(13);
		System.out.println(node);
		System.out.println(node.iData);
		System.out.println(node.dData);
		
	}
}

Traversing the Tree

Traversing a tree means visiting each node in a specified order. This process is not as
commonly used as finding, inserting, and deleting nodes. Three simple ways to traverse a tree .

• Preorder
• Inorder
• Postorder

1.Inorder Traversal (Left → Root → Right)

In order method ,we first visit the left subtree, then the root node, and finally the right subtree.
For a Binary Search Tree, inorder traversal prints elements in sorted order.

Algorithm

1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

private void inOrder(node localRoot)
{
 if(localRoot != null)
 {
   inOrder(localRoot.leftChild);
   System.out.print(localRoot.iData + “ “);
   inOrder(localRoot.rightChild);
 }
}

2. Preorder Traversal (Root → Left → Right)

In Preorder traversal, we visit the root first, then the left subtree, and finally the right subtree.
It is commonly used to create or copy a tree structure.

Algorithm

1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.

void preorder(Node node) {
    if (node == null)
        return;

    System.out.print(node.data + " "); // Visit root
    preorder(node.left);               // Visit left
    preorder(node.right);              // Visit right
}

3. Postorder Traversal (Left → Right → Root)

In postorder traversal, we visit the left subtree first, then the right subtree, and finally the root node.
This method is useful for deleting or freeing the tree nodes.

Algorithm

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root node.

void postorder(Node node) {
    if (node == null)
        return;

    postorder(node.left);   // Visit left
    postorder(node.right);  // Visit right
    System.out.print(node.data + " "); // Visit root
}

How to find Minimum and Maximum values in tree

package com.rkdigitalschool.msil.datastructure;
public class Tree {
	private Node root;
	public Tree() {
		root=null;
	}
	public void insert(int id, double dd)
	{
		Node newNode = new Node(); // make new node
		newNode.iData = id; // insert data
		newNode.dData = dd;
		if(root==null) // no node in root
			root = newNode;
		else{
			Node current = root; // start at root
			Node parent;
			while(true){
				parent = current;
				if(id < current.iData){
				      current = current.leftChild;
				      if(current == null){ 
				       parent.leftChild = newNode;
				       return;
				}
			       } // end if go left
			      else {
				 current = current.rightChild;
				 if(current == null){ 
					parent.rightChild = newNode;
					return;
					}
				} // end else go right
			} // end while
		} // end else not root
	} // end insert()

	public Node minimum() 
	{
		Node current,last=null;
		current=root;
		while(current!=null) {
			last=current;
			current=current.leftChild;
		}
		return last;
	}

	public Node Maximum() {
		Node current, last=null;
		current=root;
		while(current!=null) {
			last=current;
			System.out.println(last.iData);
			current=current.rightChild;
			System.out.println("------------");
			System.out.println(current.iData);
		}
		return last;
	}
}

What is Successor?.

Successor in a binary tree is the node that appears immediately after a given node in a specific traversal order, most commonly the inorder traversal. In a Binary Search Tree, the successor of a node is the smallest node in its right subtree.

Delete a Node in a Binary Search Tree

Deleting a node is the most complicated common operation required for binary search trees. However, deletion is important in many tree applications You start by finding the node you want to delete, using the same approach we saw in find() and insert(). When you’ve found the node, there are three cases to
consider:

• The node to be deleted has two children.
• The node to be deleted is a leaf (has no children).
• The node to be deleted has one child.

package com.test.rkdigital.school.tree;

public class DeletefrombinaryTree {
	private Node root;
	public DeletefrombinaryTree() 
	{
		root=null;
	}
	public void insert(int id, double dd)
	{
		Node newNode = new Node(); // make new node
		newNode.iData = id; // insert data
		newNode.dData = dd;
		if(root==null) // no node in root
			root = newNode;
		else{
			Node current = root; // start at root
			Node parent;
			while(true){
				parent = current;
				if(id < current.iData){
					current = current.leftChild;
					if(current == null){ 
						parent.leftChild = newNode;
						return;
					}
				} // end if go left
				else {
					current = current.rightChild;
					if(current == null){ 
						parent.rightChild = newNode;
						return;
					}
				} // end else go right
			} // end while
		} // end else not root
	} // end insert()

	public boolean delete(int key) 
	{ // (assumes non-empty list)
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;
		while(current.iData != key) // search for node
		{
			parent = current;
			if(key < current.iData) // go left?
			{
				isLeftChild = true;
				current = current.leftChild;
			}
			else // or go right?
			{
				isLeftChild = false;
				current = current.rightChild;
			}
			if(current == null) // end of the line,
				return false; // didn’t find it
		} // end while
		// found node to delete
		// if no children, simply delete it
		if(current.leftChild==null &&
				current.rightChild==null)
		{
			if(current == root) // if root,
				root = null; // tree is empty
			else if(isLeftChild)
				parent.leftChild = null; // disconnect
			else // from parent
				parent.rightChild = null;
		}
		// if no right child, replace with left subtree
		else if(current.rightChild==null)
			if(current == root)
				root = current.leftChild;
			else if(isLeftChild)
				parent.leftChild = current.leftChild;
			else
				parent.rightChild = current.leftChild;
		// if no left child, replace with right subtree
		else if(current.leftChild==null)
			if(current == root)
				root = current.rightChild;
			else if(isLeftChild)
				parent.leftChild = current.rightChild;
			else
				parent.rightChild = current.rightChild;
		else // two children, so replace with inorder successor
		{
			// get successor of node to delete (current)
			Node successor = getSuccessor(current);
			// connect parent of current to successor instead
			if(current == root)
				root = successor;
			else if(isLeftChild)
				parent.leftChild = successor;
			else
				parent.rightChild = successor;
			// connect successor to current’s left child
			successor.leftChild = current.leftChild;
		} // end else two children
		// (successor cannot have a left child)
		return true; // success
	} // end delete()

	
	private Node getSuccessor(Node delNode)
	{
		Node successorParent = delNode;
		Node successor = delNode;
		Node current = delNode.rightChild; // go to right child
		while(current != null) // until no more
		{ // left children,
			successorParent = successor;
			successor = current;
			current = current.leftChild; // go to left child
		}
		// if successor not
		if(successor != delNode.rightChild) // right child,
		{ // make connections
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}

	// find node with given key
		public Node find(int key) 
		{ 
			//start at root
			Node current = root; 
			// while no match,
			while(current.iData != key) 
			{
				if(key < current.iData) // go left?
					current = current.leftChild;
				else // or go right?
					current = current.rightChild;
				if(current == null) // if no child,
					return null; // didn’t find it
			}
			return current; // found it
		}
		
	public static void main(String[] args) {
		
		DeletefrombinaryTree theTree = new DeletefrombinaryTree();
		theTree.insert(50, 1.5);
		theTree.insert(25, 1.2);
		theTree.insert(75, 1.7);
		theTree.insert(12, 1.5);
		theTree.insert(37, 1.2);
		theTree.insert(43, 1.7);
		theTree.insert(30, 1.5);
		theTree.insert(33, 1.2);
		theTree.insert(87, 1.7);
		theTree.insert(93, 1.5);
		theTree.insert(97, 1.5);
		
		
		System.out.println(theTree.find(43));
		System.out.println(theTree.delete(43));
		System.out.println("----------------");
		System.out.println(theTree.find(43));
		
		
	}
}

Complete Example :

1. Node.java

package com.test.rkdigital.school.tree;

public class Node {

	public int iData; // data item (key)
	public double dData; // data item
	public Node leftChild; // this node’s left child
	public Node rightChild; // this node’s right child

	public void displayNode() // display ourself
	{
		System.out.print('{');
		System.out.print(iData);
		System.out.print(",");
		System.out.print(dData);
		System.out.print("} ");
	}
}

2. Tree.java

package com.test.rkdigital.school.tree;

import java.io.*;
import java.util.*;

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

	public Node find(int key) // find node with given key
	{ // (assumes non-empty tree)
		Node current = root; // start at root
		while(current.iData != key) // while no match,
		{
			if(key < current.iData) // go left?
				current = current.leftChild;
			else // or go right?
				current = current.rightChild;
			if(current == null) // if no child,
				return null; // didn’t find it
		}
		return current; // found it
	} // end find()

	public void insert(int id, double dd)
	{
		Node newNode = new Node(); // make new node
		newNode.iData = id; // insert data
		newNode.dData = dd;
		if(root==null) // no node in root
			root = newNode;
		else // root occupied
		{
			Node current = root; // start at root
			Node parent;
			while(true) // (exits internally)
			{
			  parent = current;
			  if(id < current.iData) // go left?
			  {
			    current = current.leftChild;
			    if(current == null) // if end of the line,
			     { // insert on left
			       parent.leftChild = newNode;
			       return;
			      }
			   } // end if go left
			else // or go right?
			{
			  current = current.rightChild;
			  if(current == null) // if end of the line
			  { // insert on right
			   parent.rightChild = newNode;
			   return;
			   }
			} // end else go right
		    } // end while
		} // end else not root
	} // end insert()
	
     // delete node with given key
	public boolean delete(int key) 
	{ // (assumes non-empty list)
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;
		while(current.iData != key) // search for node
		{
			parent = current;
			if(key < current.iData) // go left?
			{
				isLeftChild = true;
				current = current.leftChild;
			}
			else // or go right?
			{
				isLeftChild = false;
				current = current.rightChild;
			}
			if(current == null) // end of the line,
				return false; // didn’t find it
		} // end while
		// found node to delete
		// if no children, simply delete it
		if(current.leftChild==null &&
				current.rightChild==null)
		{
			if(current == root) // if root,
				root = null; // tree is empty
			else if(isLeftChild)
				parent.leftChild = null; // disconnect
			else // from parent
				parent.rightChild = null;
		}
		// if no right child, replace with left subtree
		else if(current.rightChild==null)
			if(current == root)
				root = current.leftChild;
			else if(isLeftChild)
				parent.leftChild = current.leftChild;
			else
				parent.rightChild = current.leftChild;
		// if no left child, replace with right subtree
		else if(current.leftChild==null)
			if(current == root)
				root = current.rightChild;
			else if(isLeftChild)
				parent.leftChild = current.rightChild;
			else
				parent.rightChild = current.rightChild;
		else // two children, so replace with inorder successor
		{
			// get successor of node to delete (current)
			Node successor = getSuccessor(current);
			// connect parent of current to successor instead
			if(current == root)
				root = successor;
			else if(isLeftChild)
				parent.leftChild = successor;
			else
				parent.rightChild = successor;
			// connect successor to current’s left child
			successor.leftChild = current.leftChild;
		} // end else two children
		// (successor cannot have a left child)
		return true; // success
	} // end delete()
	
	private Node getSuccessor(Node delNode)
	{
		Node successorParent = delNode;
		Node successor = delNode;
		Node current = delNode.rightChild; // go to right child
		while(current != null) // until no more
		{ // left children,
		  successorParent = successor;
		  successor = current;
		  current = current.leftChild; // go to left child
		}
		// if successor not
		if(successor != delNode.rightChild) // right child,
		{ // make connections
		   successorParent.leftChild = successor.rightChild;
		   successor.rightChild = delNode.rightChild;
		}
		return successor;
	}
	// -------------------------------------------------------------
	public void traverse(int traverseType)
	{
		switch(traverseType)
		{
		case 1: System.out.print("\nPreorder traversal: ");
		preOrder(root);
		break;
		case 2: System.out.print("\nInorder traversal: ");
		inOrder(root);
		break;
		case 3: System.out.print("\nPostorder traversal: ");
		postOrder(root);
		break;
		}
		System.out.println();
	}
	private void preOrder(Node localRoot)
	{
		if(localRoot != null)
		{
			System.out.print(localRoot.iData + " ");
			preOrder(localRoot.leftChild);
			preOrder(localRoot.rightChild);
		}
	}

	private void inOrder(Node localRoot)
	{
		if(localRoot != null)
		{
			inOrder(localRoot.leftChild);
			System.out.print(localRoot.iData + " ");
			inOrder(localRoot.rightChild);
		}
	}

	private void postOrder(Node localRoot)
	{
		if(localRoot != null)
		{
			postOrder(localRoot.leftChild);
			postOrder(localRoot.rightChild);
			System.out.print(localRoot.iData + " ");
		}
	}
	// -------------------------------------------------------------
	public void displayTree()
	{
		Stack globalStack = new Stack();
		globalStack.push(root);
		int nBlanks = 32;
		boolean isRowEmpty = false;
		System.out.println("......................................................");
		while(isRowEmpty==false)
		{
			Stack localStack = new Stack();
			isRowEmpty = true;
			for(int j=0; j<nBlanks; j++)
				System.out.print(' ');
			while(globalStack.isEmpty()==false)
			{
				Node temp = (Node)globalStack.pop();
				if(temp != null)
				{
				 System.out.print(temp.iData);
				 localStack.push(temp.leftChild);
				 localStack.push(temp.rightChild);
				 if(temp.leftChild != null ||
					temp.rightChild != null)
					isRowEmpty = false;
				}
				else
				{
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				for(int j=0; j<nBlanks*2-2; j++)
					System.out.print(' ');
			} // end while globalStack not empty
			System.out.println();
			nBlanks /= 2;
			while(localStack.isEmpty()==false)
				globalStack.push( localStack.pop() );
		} // end while isRowEmpty is false
	} // end displayTree()
} 

3.TreeApp.java

package com.test.rkdigital.school.tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TreeApp 
{
	public static void main(String[] args) throws IOException
	{
	   int value;
	   Tree theTree = new Tree();
	   theTree.insert(50, 1.5);
	   theTree.insert(25, 1.2);
	   theTree.insert(75, 1.7);
	   theTree.insert(12, 1.5);
	   theTree.insert(37, 1.2);
	   theTree.insert(43, 1.7);
	   theTree.insert(30, 1.5);
	   theTree.insert(33, 1.2);
	   theTree.insert(87, 1.7);
	   theTree.insert(93, 1.5);
	   theTree.insert(97, 1.5);
	   while(true){
	    System.out.print("Enter first letter of show ");
	    System.out.print("insert, find, delete, or traverse:");
	    int choice = getChar();
	    switch(choice)
	    {
		case 's':
		   theTree.displayTree();
		   break;
		case 'i':
		   System.out.print("Enter value to insert: ");
		   value = getInt();
		   theTree.insert(value, value + 0.9);
		   break;
		case 'f':
		   System.out.print("Enter value to find:");
		   value = getInt();
		   Node found = theTree.find(value);
		    if(found != null)
		     {
			System.out.print("Found: ");
			found.displayNode();					  
                        System.out.print("\n");
		      }
			else
			System.out.print("Could not find ");
			System.out.print(value + "\n");
			break;
		 case 'd':
			System.out.print("Enter value to delete: ");
			value = getInt();
			boolean didDelete = theTree.delete(value);
			if(didDelete)
			   System.out.print("Deleted " + value);
			else
			   System.out.print("Could not delete ");
			   System.out.print(value + "\n");
			   break;
		  case 't':
			System.out.print("Enter type 1, 2 or 3:");
			value = getInt();
			theTree.traverse(value);
			break;
		   default:
			System.out.print("Invalid entry\n");
			} // end switch
		} // end while
	} // end main()
	// -------------------------------------------------------------
	public static String getString() throws IOException
	{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}

	public static char getChar() throws IOException
	{
		String s = getString();
		return s.charAt(0);
	}

	public static int getInt() throws IOException
	{
		String s = getString();
		return Integer.parseInt(s);
	}
}