A tree is a graph whose degree of node==# of it's children & is acyclic
Binary tree is a tree with each node having atmost 2 children.2 ways to traverse each node once:
BFS - level wise
DFS - BY RECURSIVELY TRAVERSING ROOT,LEFT SUBTREE (L)& RIGHT SUBTREE (R)
NOTE: THERE ARE 3! WAYS OF DOING A DFS, BASED ON ORDER OF Root,L,R.
but only 3 are useful :
Root,L,R- preorder traversal
L,Root,R- inorder traversal
L,R,Root- postorder traversal
//BINARY TREE TRAVERSAL
//---------------------
public classtraversal{
public static void main(String[] args){
treetraversal t = new treetraversal();
t.root = new node('A');// initializing the root node
t.root.left = new node('B');// initializing the left node
t.root.right = new node('C');// initializing the right node
t.root.left.left = new node('D');// initializing the sub-left node of the left node
t.root.left.right = new node('E');// initializing the sub-right node of the left node
t.root.right.left = new node('F');// initializing the sub-left node of the right node
t.root.right.right = new node('G');// initializing the sub-right node of the right node
//this tree can be made as large as the we want it to be by adding further sub nodes
System.out.println("IN ORDER TRAVERSAL");
t.InOrderTraversal(t.root);
System.out.println();
System.out.println();
System.out.println("PRE ORDER TRAVERSAL");
t.PreOrderTraversal(t.root);
System.out.println();
System.out.println();
System.out.println("POST ORDER TRAVERSAL");
t.PostOrderTraversal(t.root);}}classnode{//as there are nodes in trees
char key;//as every node has a value or key
node left,right;//as every node will have a left and a right child
node(char KEY){
this.key = KEY;}}classtreetraversal{/*there are thre types of traversals
1. InOrder Traversal
2. PreOrder Traversal
3.PostOrder Traversal
*/
node root;//as every tree has a root node to which there exist left and right nodes
void InOrderTraversal(node n){//InOrder Traversal = Left Root Right
if(n!=null){
InOrderTraversal(n.left);
System.out.print(n.key +" ");
InOrderTraversal(n.right);}}
void PreOrderTraversal(node n){//PreOrder Traversal = Root Left Right
if(n!=null){
System.out.print(n.key +" ");
PreOrderTraversal(n.left);
PreOrderTraversal(n.right);}}
void PostOrderTraversal(node n){//PostOrder Traversal = Left Right Root
if(n!=null){
PostOrderTraversal(n.left);
PostOrderTraversal(n.right);
System.out.print(n.key +" ");}}}
How to perform in-order traversal of a binary tree?
/*
This is an implementation that collects the
values of the nodes of a binary tree by performing
an in-order traversal of the tree.
Let n be the number of binary tree nodes
Time complexity: O(n)
Space complexity: O(n)*/import java.util.List;import java.util.ArrayList;
public classBTInOrderTraversal{
private BTNode BTRoot;
public BTInOrderTraversal(){/** Create tree below:*1**2*/*3*/
BTRoot = new BTNode(1, null, null);
BTNode rootRight = new BTNode(2, null, null);
BTRoot.right = rootRight;
BTNode rootRightLeft = new BTNode(3, null, null);
rootRight.left = rootRightLeft;}
public static void main(String[] args){
BTInOrderTraversal application = new BTInOrderTraversal();
List<Integer> values = application.inorderTraversal();
System.out.println(values);//[1,3,2]}// Perform in-order traversal through the tree.
public List<Integer> inorderTraversal(){
List<Integer>list= new ArrayList<>();
populateList(BTRoot,list);returnlist;}// Helper method to populate list by performing
//in-order traversal through the tree.
private void populateList(BTNode root, List<Integer>list){if(root == null){return;}if(root.left != null){
populateList(root.left,list);}list.add(root.val);if(root.right != null){
populateList(root.right,list);}}// Class representing a binary tree node
//with pointers to value, left,and right nodes
private classBTNode{int val;
BTNode left;
BTNode right;
public BTNode(int val, BTNode left, BTNode right){
this.val = val;
this.left = left;
this.right = right;}}}