Traversal of Binary Tree

Introduction

Binary trees are an essential data structure used in computer science and programming. They offer a productive means of storing and organizing data hierarchically. We might lead various procedures on the tree's elements by visiting every node in a specific request while navigating a binary tree. In this article, we will analyze the possibility of binary tree crossing, as well as its many structures and uses. We will likewise go through a few other tree-crossing techniques,

Overview

Binary trees are hierarchical data structures made up of nodes. Every node in a binary tree has worth and, if relevant, pointers on its left side and right child nodes. The root node of the tree is the principal node, and every node has a limit of two children. Because of their flexibility and effortlessness in portraying different genuine settings, including record frameworks, dynamic cycles, and hierarchical connections, binary trees are frequently utilized.

What are Binary Trees?

A binary tree consists of nodes connected by edges. Each node includes references to its left and right child nodes and the ability to store data. A binary tree's structure ensures that each node has a maximum of two offspring, which facilitates efficient navigation and operation. This is an illustration of a binary tree:

Example:

7

/ \

4 9

/ \ /

2 5 8

The "7" node in the model above is the root node. It has a right youngster node with the mark "9" and a left kid node with the name "4". The node "4" contains two kid nodes with the marks "2" and "5" on the left and right, individually. The node "9" has a left kid node named "8".

What is Traversing?

The act of viewing each node in a data structure in a certain sequence is known as traversing. In the context of binary trees, traversing entails precisely one visit to each node. This operation is crucial for accessing and processing the data stored in the tree effectively. By applying different traversal techniques, we can explore the nodes of a binary tree in different orders.

What is the Traversal of a Binary Tree?

A binary tree may be traversed by going through each node in turn. Inorder, preorder, and postorder traversals are the three most prevalent forms. Nodes are visited in the following order during inorder traversal: left subtree, current node, then right subtree. Preorder traversal visits the ongoing node before its youngsters, and postorder crossing visits the ongoing node after its kids.

Here's an example:

• Inorder traversal: 1 -> 3 -> 5 -> 7 -> 8 -> 9
• Preorder traversal: 7 -> 3 -> 1 -> 5 -> 9 -> 8
• Postorder traversal: 1 -> 5 -> 3 -> 8 -> 9 -> 7

It is possible to conduct operations like finding, adding, removing, or printing the data contained in the tree thanks to traversal of binary tree in C++, which enables us to process the nodes in a certain sequence.

Types of Binary Tree Traversal

There are several types of binary tree traversals as listed below:

• Inorder Traversal

The left subtree is visited first during the inorder traversal, then the root node, and finally the right subtree. When used with binary search trees, this traversal strategy produces nodes in non-decreasing order.

Here is the algorithm for inorder traversal:

Algorithm Inorder(tree):

• Traverse the left subtree, i.e., call Inorder(left->subtree).
• Visit the root.
• Traverse the right subtree, i.e., call Inorder(right->subtree).

Java example of inorder traversal:

java
class Node { 
    int data; 
    Node left, right; 
 
    public Node(int item) { 
        data = item; 
        left = right = null; 
    } 
} 
 
class BinaryTree { 
    Node root; 
 
    BinaryTree() { 
        root = null; 
    } 
 
    void inorder traversal(Node node) { 
        if (node == null) 
            return; 
 
        inorderTraversal(node.left); 
        System.out.print(node.data " "); 
        inorderTraversal(node.right); 
    } 
 
    public static void main(String[] args) { 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(7); 
        tree.root.left = new Node(4); 
        tree.root.right = new Node(9); 
        tree.root.left.left = new Node(2); 
        tree.root.left.right = new Node(5); 
        tree.root.right.left = new Node(8); 
 
        System.out.println("Inorder traversal: "); 
        tree.inorderTraversal(tree.root); 
    } 
}  

Output:

yamlCopy code 
Inorder traversal: 
2 4 5 7 8 9  

Uses of Inorder Traversal:

• Inorder traversal of binary tree in data structure is useful when we need to retrieve the elements of a binary search tree in sorted order.
• It is often used to evaluate arithmetic expressions in postfix notation.

• Preorder Traversal

In the preorder traversal, the root node is visited first, followed by the left subtree and then the right subtree. Here is the algorithm for preorder traversal:

Algorithm Preorder(tree):

• Visit the root.
• Traverse the left subtree, i.e., call Preorder(left->subtree).
• Traverse the right subtree, i.e., call Preorder(right->subtree).

Java example of preorder traversal:

java
class Node { 
    int data; 
    Node left, right; 
 
    public Node(int item) { 
        data = item; 
        left = right = null; 
    } 
} 
 
class BinaryTree { 
    Node root; 
 
    BinaryTree() { 
        root = null; 
    } 
 
    void preorderTraversal(Node node) { 
        if (node == null) 
            return; 
 
        System.out.print(node.data " "); 
        preorderTraversal(node.left); 
        preorderTraversal(node.right); 
    } 
 
    public static void main(String[] args) { 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(7); 
        tree.root.left = new Node(4); 
        tree.root.right = new Node(9); 
        tree.root.left.left = new Node(2); 
        tree.root.left.right = new Node(5); 
        tree.root.right.left = new Node(8); 
 
        System.out.println("Preorder traversal: "); 
        tree.preorderTraversal(tree.root); 
    } 
}  

Output:

yamlCopy code 
Preorder traversal: 
7 4 2 5 9 8 

Uses of Preorder Traversal:

• Preorder traversal is used to create a copy of a binary tree.
• It helps convert an expression from infix to postfix notation.

• Postorder Traversal

In the postorder traversal of binary tree, the left and right subtrees are visited before the root node. Here is the algorithm for postorder traversal:

Algorithm Postorder(tree):

• Traverse the left subtree, i.e., call Postorder(left->subtree).
• Traverse the right subtree, i.e., call Postorder(right->subtree).
• Visit the root.

Java example of postorder traversal:

java
class Node { 
    int data; 
    Node left, right; 
 
    public Node(int item) { 
        data = item; 
        left = right = null; 
    } 
} 
 
class BinaryTree { 
    Node root; 
 
    BinaryTree() { 
        root = null; 
    } 
 
    void postorderTraversal(Node node) { 
        if (node == null) 
            return; 
 
        postorderTraversal(node.left); 
        postorderTraversal(node.right); 
        System.out.print(node.data " "); 
    } 
 
    public static void main(String[] args) { 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(7); 
        tree.root.left = new Node(4); 
        tree.root.right = new Node(9); 
        tree.root.left.left = new Node(2); 
        tree.root.left.right = new Node(5); 
        tree.root.right.left = new Node(8); 
 
        System.out.println("Postorder traversal: "); 
        tree.postorderTraversal(tree.root); 
    } 
} 

Output:

yamlCopy code 
Postorder traversal: 
2 5 4 8 9 7 

Uses of Postorder Traversal:

• Postorder traversal is commonly used in deleting or freeing nodes of a binary tree.
• It is useful to use traversal of binary tree calculator for performing certain mathematical calculations such as evaluating the value of a postfix expression.

Some other Tree Traversal Techniques

There are some additional tree traversing techniques as mentioned below:

• Level Order Traversal: From left to right, this crossing strategy navigates every node at each level of the tree. It starts from the root, goes to the principal level's node, then, at that point, forges ahead to the second level's node, etc. A line information design might be used to accomplish this cross. The binary tree's level request crossing in the illustration below is 1-2-3-4-5-6-7.
• Boundary Traversal: The tree's leaves, right border, and left and right boundaries are all taken into account when the boundary traversal algorithm moves over the tree's nodes. The traversal of the left boundary, the traversal of the leaf, and the traversal of the right border may be divided into these three categories. The boundary traversal of the binary tree in the example below is 1-2-4-7-8-9-10-6-3.
• Diagonal Traversal: From the top-left to the bottom-right of the tree, a diagonal traversal travels, stopping at each node along the way. It travels along each diagonal line, halting at each node separately, starting at the leftmost node of the tree. For instance, the diagonal traversal of binary tree python in the following picture is 1-2-4-3-5-7-6.

Conclusion

Understanding and working with these hierarchical data structures require the traversal of binary tree example. In this article, we looked at the inorder, preorder, and postorder traversal approaches. We also spoke about each traversal's applications and gave a quick introduction to alternative traversal strategies such as level order, boundary, and diagonal traversals. By mastering these traversal of binary tree in C techniques, developers can efficiently navigate binary trees and perform various operations on their nodes.

FAQs

1. Why is traversal important in binary trees?

Traversal is important in binary trees as it allows us to access and process each node in a specific order. It makes it possible to do operations like finding, removing, adding, or printing values kept in the tree.

2. What distinguishes inorder, preorder, and postorder traversal from one another?

In an inorder traversal, the left subtree, the ongoing node, and the right subtree are visited in a specific order. Preorder crossing visits the ongoing node before its kids, while postorder crossing visits the ongoing node after its youngsters.

3. Can I perform different traversals on the same binary tree?

Yes, you can perform different traversals on the same binary tree. Each traversal visits the nodes in a specific order, allowing you to process the tree's elements differently based on your requirements.

4. How is traversal useful in binary tree algorithms?

Traversal is essential in binary tree algorithms as it provides a way to explore the structure of the tree and perform operations on its nodes. Algorithms like tree sorting, expression evaluation, and constructing tree representations rely on traversal.

5. Are there any further tree traversal types?

In addition to inorder, preorder, and postorder tree crossings, there are extra sorts too, including level request crossing (expansiveness first crossing), in which nodes are visited by levels going from start to finish and left to right. These crossings have various purposes and can be applied given the specific states of the recent concern.