A Binary Tree is a variety of Trees that has a maximum of two children. It has three parts mainly Associated with it i.e
Root Node
Left Node(Left Child)
Right Node(Right Child)
What are the Types of Binary Trees?
1-Full Binary Tree: It is a variety of Binary Tree With either zero or two Nodes as Children.
2-Complete Binary Tree: It is a type of Binary Tree in which all Levels of a Binary Tree are Filled except the last Level of the Binary Tree.
3-Perfect Binary Tree:It is a type of Binary Tree in which all levels are filled. A unique point about a perfect Binary Tree is no leaf node (node at last level is internal node plus one).
4-Balanced Binary tree(AVL tree): It is a type of Binary Tree in which the difference b/w left and right subTree is a max of one. It is also known as the AVL tree.
5-Degenerate Tree: It is a Binary Tree Where every Node has either Zero or one parent.
Different Types of Traversal in Binary Tree
Traversal in Binary Tree is Mainly done in three ways, and that is:
1: In order Traversal This is a variety of Depth tree traversal in which First, we traverse the left part of the tree using Recursion, then cross the root node, and then we travel the right amount of the tree.
Algorithm A:-Traverse the left subtree.(i.e call Inorder(root->left). B:-Visit The RootNode. C:-Traverse the Right half of the Binary Tree(i.e. call Inorder(root->right).
Output:4,2,5,1,6,3,7;
Benefits of Inorder Traversal The main benefit of inorder traversal is it gives nodes in non -Decreasing order .it can also be used to get the nodes of Binary Sorted Tree using its variation
2: Pre-Order Traversal This is a variety of Depth Binary Tree Traversal in Which First we Visit the Root then we visit the right half of the Tree, and then we visit the left half of the Binary tree.
Algorithm A:-Visit the Root Node. B:-Traverse the left subtree.(i.e call Pre-order(root->left). C:-Traverse the Right half of the Binary Tree(i.e. call Pre-Order(root->right).
Output: 1,2,4,5,3,6,7;
Benefits of Pre-OrderTraversal For Creating a Copy Of the Tree Preorder Traversal is used. It is also used to get Prefix -expression Of an Expression Tree. the
3: Post-Order Traversal It is a variety of Depth Binary Traversal in which First we Traverse the Left Subtree, and then we traverse Right Subtree, then We Traverse the Root Node.
Algorithm: A:-Traverse the left subtree.(i.e call Post-order(root->left). B:-Traverse the Right half of the Binary Tree(i.e. call POst-Order(root->right). C:-Visit the Root Node.
Output:4,5,2,1,6,3,7;
Before proceeding, let's watch the below video to see how Preorder, Inorder, and Postorder traversals are implemented in both recursive and iterative fashion.
Advantages of Postorder traversal in Binary Tree
It is used to delete a given Binary Tree. It is also the used to get Postfix Expression of an Expression Tree.
Code in java:
//Binary Tree Node
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
//Main Class
class BinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root = null; }
/* postorder traversal. */
void printPostorder(Node node)
{
//Base case
if (node == null)
return;
//left traversal
printPostorder(node.left);
//right traversal
printPostorder(node.right);
//visit root node
System.out.print(node.key + " ");
}
/*inorder*/
void printInorder(Node node)
{
//Base case
if (node == null){
return;
}
//left sub Tree
printInorder(node.left);
//Root node
System.out.print(node.key + " ");
//Right node
printInorder(node.right);
}
/* print Binary Tree in preorder*/
void printPreorder(Node node)
{
if (node == null){
return;
}
System.out.print(node.key + " ");
printPreorder(node.left);
printPreorder(node.right);
}
// Wrappers over above recursive functions
void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }
// Driver method
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
//Pre-order Traversal in Binary Tree
tree.printPreorder();
//Inorder traversal in Binary Tree
tree.printInorder();
//PostOrder Traversal in Binary Tree
tree.printPostorder();
}
}
Breadth-first traversal
It is a variety of binary-tree traversal in which we first traverse all the nodes at the current level then we move to the next level of the binary tree.
Algorithm: Create a queue in which add the root node, then add the null and start to print the element of the queue by removing that element and adding all its children in the queue, once null is encountered that means we have moved to the next level.
305+ registered