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

Inorder Implementation

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