Exploring Binary Trees and Inorder Traversal

Venkys.io

Exploring Binary Trees and Inorder Traversal

Introduction to Trees

A tree is a hierarchical data structure which is composed of nodes, where each node has at maximum two children and they are called as left child and right child. This interconnected system is reminiscent of an upside-down tree, with the topmost node called the root. In this structure, nodes hold data, and edges represent connections between nodes. Trees play a crucial role in computer science, serving as versatile tools for tasks such as searching, sorting, and analysis. Each node's ability to have multiple children allows for the creation of complex hierarchical relationships, making trees an indispensable concept for organizing and manipulating data efficiently. Whether utilized for representing hierarchical relationships, optimizing search algorithms, or structuring databases, trees form a foundational element in computer science, contributing to the systematic and effective management of information.

Introduction to Inorder Traversal

Inorder traversal is a method of traversing a binary tree in a specific order. It starts from the leftmost node and moves towards the rightmost node, visiting the left subtree first, then the root, and finally the right subtree. This traversal strategy is fundamental for exploring and processing binary trees systematically.

Overview

The provided Python code defines a binary tree node using a class named Node and demonstrates recursive inorder traversal. The Node class has a constructor initializing the node with some data and two pointers, left and right, representing the left and right children.

Step-by-Step Explanation

Using Python

code

class Node:
    def __init__(self,data):
        self.data=data 
        self.left=self.right=None 
# Recursive Inorder Traversal.
def inorder(root):
    # Check if the root exists
    if root:
        # Perform an inorder traversal on the left subtree
        inorder(root.left)
        # Print the value of the current node
        print(root.data,end=" ")
        # Perform an inorder traversal on the right subtree
        inorder(root.right)
    # Driver code to test above function 
# The values of nodes are given below :
if __name__=="__main__":
    root_data = int(input())
    root = Node(root_data)

    left_data = int(input())
    if left_data != -1:
        root.left = Node(left_data)

    right_data = int(input())
    if right_data != -1:
        root.right = Node(right_data)

    left_left_data = int(input())
    if left_left_data != -1:
        root.left.left = Node(left_left_data)

    left_right_data = int(input())
    if left_right_data != -1:
        root.left.right = Node(left_right_data)

    right_left_data = int(input())
    if right_left_data != -1:
        root.right.left = Node(right_left_data)

    right_right_data = int(input())
    if right_right_data != -1:
        root.right.right = Node(right_right_data)
    inorder(root)

Explanation:

Node Class Definition:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

This class defines the structure of a binary tree node. Each node has a data attribute to store the value of the node, and left and right attributes to point to the left and right children, respectively.

Inorder Traversal Function:

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

This function, inorder, is a recursive implementation of the inorder traversal algorithm. It takes a root node as an argument and performs the following steps: => Check if the current root exists. => Recursively traverse the left subtree. => Print the value of the current node. => Recursively traverse the right subtree.

3.Driver Code and Tree Initialization

 if __name__ == "__main__":
    root = Node(80)
    root.left = Node(20)
    root.right = Node(30)
    root.left.left = Node(40)
    root.left.right = Node(350)
    root.right.left = Node(460)
    root.right.right = Node(70)

In the main block, a binary tree is created with the following structure:

  80
 /  \
20   30

/ \ /
40 350 460 70

Inorder Traversal Call

       inorder(root)

This line calls the inorder function with the root of the tree, initiating the inorder traversal. The result is the values of the nodes printed in ascending order.

In summary, the code defines a binary tree, initializes it with specific values, and then performs an inorder traversal, printing the values of the nodes in ascending order. The recursive nature of the inorder function is key to traversing the tree systematically.

using C++

code

#include<bits/stdc++.h>

class Node{
    public:
        int data;
        Node *left=NULL;
        Node *right=NULL;

        // Node constructor initializes data
        Node(int val){
            data=val;
        }
};
void inorder(Node* root){
    // call inorder for left subtree
    if(root!=NULL){
        inorder(root->left);
        // Print root node data
        std::cout<<root->data<<" ";
        // call inorder for right subtree
        inorder(root->right);
    }
}

int main(){
    // Creating the binary tree
    int value;
    // std::cout << "Enter value for root node: ";
    std::cin >> value;
    Node* root = new Node(value);

    // std::cout << "Enter value for left child of root node (or -1 if none): ";
    std::cin >> value;
    if (value != -1)
        root->left = new Node(value);

    // std::cout << "Enter value for right child of root node (or -1 if none): ";
    std::cin >> value;
    if (value != -1)
        root->right = new Node(value);

    // std::cout << "Enter value for left child of left child of root node (or -1 if none): ";
    std::cin >> value;
    if (value != -1 && root->left != nullptr)
        root->left->left = new Node(value);

    // std::cout << "Enter value for right child of left child of root node (or -1 if none): ";
    std::cin >> value;
    if (value != -1 && root->left != nullptr)
        root->left->right = new Node(value);

    // std::cout << "Enter value for left child of right child of root node (or -1 if none): ";
    std::cin >> value;
    if (value != -1 && root->right != nullptr)
        root->right->left = new Node(value);

    // std::cout << "Enter value for right child of right child of root node (or -1 if none): ";
    std::cin >> value;
    if (value != -1 && root->right != nullptr)
        root->right->right = new Node(value);

    // Displaying the binary tree in inorder traversal
    inorder(root);
    // Inorder traversal of the tree
    return 0;
}

Explanation

Header Inclusion:
```
#include<bits/stdc++.h>
```
This line includes a standard C++ library header, which is a common practice to include necessary headers like <iostream> for input and output.
Node Class Definition:
```
class Node {
public:
    int data;
    Node *left = NULL;
    Node *right = NULL;

    // Node constructor initializes data
    Node(int val) {
        data = val;
    }
};
```
This part defines a Node class representing nodes in a binary tree. Each node contains an integer data, a pointer to the left child (left), and a pointer to the right child (right). The constructor initializes the node with the provided data value.

Inorder Traversal Function:

void inorder(Node* root) {
    // call inorder for the left subtree
    if (root != NULL) {
        inorder(root->left);
        // Print root node data
        std::cout << root->data << " ";
        // call inorder for the right subtree
        inorder(root->right);
    }
}

The inorder function performs recursive inorder traversal on the binary tree. It prints the data of each node in ascending order by first traversing the left subtree, then printing the root node's data, and finally traversing the right subtree.

Main Function:

int main() {
    // Creating the binary tree
    Node* root = new Node(10);
    root->left = new Node(20);
    root->right = new Node(30);
    root->left->left = new Node(40);
    root->left->right = new Node(50);
    root->right->left = new Node(60);
    root->right->right = new Node(70);

    // Displaying the binary tree in inorder traversal
    inorder(root);

    // Inorder traversal of the tree
    return 0;
}

In the main function, a binary tree is created with specific values. Nodes are allocated dynamically using the new keyword. The inorder function is then called to display the binary tree in inorder traversal, printing the values of the nodes in ascending order.

In summary, this C++ program defines a binary tree using a Node class, creates a binary tree with specific values, and performs an inorder traversal to display the tree's content. The code demonstrates the concept of recursive traversal in a binary tree. This code will output 40 20 50 10 60 30 70, which is a correct

using Java

Code

class TreeNode {
    int data; 
    // Store integer data
    TreeNode left = null,         
    // Left child reference
             right = null;         
    // Right child reference

    public TreeNode(int data) {   
     // Constructor to create a new TreeNode
        this.data = data;           
    // Assign the given data to this node
    }
}

public class BinaryTree {
// Method for inorder traversal

    static void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.data + " ");
            inorderTraversal(root.right);
        }
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // Input for the value of the root node
        // System.out.print("Enter value for root node: ");
        int rootValue = scanner.nextInt();
        TreeNode root = new TreeNode(rootValue);

        // Input for the left child of the root node
        // System.out.print("Enter value for left child of root node (or -1 if none): ");
        int leftChildValue = scanner.nextInt();
        if (leftChildValue != -1)
            root.left = new TreeNode(leftChildValue);

        // Input for the right child of the root node
        // System.out.print("Enter value for right child of root node (or -1 if none): ");
        int rightChildValue = scanner.nextInt();
        if (rightChildValue != -1)
            root.right = new TreeNode(rightChildValue);

        // Input for the left child of the left child of the root node
        if (root.left != null) {
            // System.out.print("Enter value for left child of left child of root node (or -1 if none): ");
            int leftLeftChildValue = scanner.nextInt();
            if (leftLeftChildValue != -1)
                root.left.left = new TreeNode(leftLeftChildValue);
        }

        // Input for the right child of the left child of the root node
        if (root.left != null) {
            // System.out.print("Enter value for right child of left child of root node (or -1 if none): ");
            int leftRightChildValue = scanner.nextInt();
            if (leftRightChildValue != -1)
                root.left.right = new TreeNode(leftRightChildValue);
        }

        // Input for the left child of the right child of the root node
        if (root.right != null) {
            // System.out.print("Enter value for left child of right child of root node (or -1 if none): ");
            int rightLeftChildValue = scanner.nextInt();
            if (rightLeftChildValue != -1)
                root.right.left = new TreeNode(rightLeftChildValue);
        }

        // Input for the right child of the right child of the root node
        if (root.right != null) {
            // System.out.print("Enter value for right child of right child of root node (or -1 if none): ");
            int rightRightChildValue = scanner.nextInt();
            if (rightRightChildValue != -1)
                root.right.right = new TreeNode(rightRightChildValue);
        }

        // Close the scanner
        scanner.close();

        // Printing the message before performing inorder traversal
        // System.out.print("Inorder Traversal: ");

        // Calling the inorderTraversal method to perform inorder traversal
        inorderTraversal(root);
    }
}

explanation

TreeNode Class Definition:
```
class TreeNode {
    int data;
    TreeNode left = null, right = null;

    public TreeNode(int data) {
        this.data = data;
    }
}
```
- TreeNode class defines the structure of a binary tree node.
- It has an int variable data to store the node's value and references (left and right) to its left and right children.
- The constructor initializes a new TreeNode with the given data.
BinaryTree Class:
```
public class BinaryTree {
    // Method for inorder traversal

    static void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.data + " ");
            inorderTraversal(root.right);
        }
    }
```
- This class contains a method inorderTraversal that performs recursive inorder traversal on a binary tree.
- It prints the data of each node in ascending order by first traversing the left subtree, then printing the root node's data, and finally traversing the right subtree.
- InorderTraversal` is a static method used for inorder traversal of the binary tree.
- It is a recursive function that traverses the left subtree, prints the data of the current node, and then traverses the right subtree.

Main Method:

public static void main(String[] args) {
    // Creating a binary tree with root node having data 10
    TreeNode root = new TreeNode(10);

    // Adding nodes to the root of the created binary tree
    // Adding left and right child nodes to the root
    root.left = new TreeNode(20);
    root.right = new TreeNode(30);

    // Adding left and right child nodes to the left child of the root
    root.left.left = new TreeNode(40);
    root.left.right = new TreeNode(50);

    // Adding left and right child nodes to the right child of the root
    root.right.left = new TreeNode(60);
    root.right.right = new TreeNode(70);

    // Printing the message before performing inorder traversal
    System.out.print("Inorder Traversal: ");

    // Calling the inorderTraversal method to perform inorder traversal
    inorderTraversal(root);
}

The main method is the entry point of the program.
It creates an instance of the TreeNode class, representing the root of the binary tree, with a data value of 10.
Child nodes are added to the root, forming a binary tree structure.
The inorderTraversal method is called to perform an inorder traversal of the tree, printing the nodes in ascending order.

Tree Structure:

     10
    /  \
   20   30
  / \  / \
 40 50 60 70

Output:

Inorder Traversal: 40 20 50 10 60 30 70

In summary, this Java program demonstrates the creation of a binary tree, addition of nodes, and the execution of an inorder traversal. The TreeNode class encapsulates the node structure, and the BinaryTree class utilizes it to construct and traverse the binary tree.

Time and Space Complexity Analysis

Time Complexity: The time complexity of the inorder traversal is O(n), where n is the number of nodes in the tree. This is because each node is visited once.
Space Complexity: The space complexity is O(h), where h is the height of the binary tree. In the worst case (skewed tree), the height is n, making the space complexity O(n). In a balanced tree, the height is log(n), resulting in a space complexity of O(log(n)).

Real-World Applications

Binary trees and inorder traversal have applications in various domains, including:

Database Indexing: Binary trees are used in database systems to efficiently index and search for records.
Expression Trees: In compilers, expression trees are used to represent mathematical expressions for efficient evaluation.
File Systems: File systems often use tree structures to organize and locate files efficiently.

Test Cases:

Input: Values of Nodes: The user inputs the values of each node in the binary tree. If a node does not have a left or right child, the user enters -1.

For example, let's consider the following input: 1 2 3 4 -1 5 -1 -1 6

Output: The output will be the inorder traversal of the constructed binary tree. For the provided input, the output would be: 4 2 1 5 3 6

Explanation: Input Interpretation:
- The user inputs the value of the root node, which is 1.
- Then, the user inputs the values of the left and right children of the root node, which are 2 and 3, respectively.
- Further, the user inputs the values of the left child's left child, which is 4.
- Then, the user inputs the value of the left child's right child, which is -1, indicating that there is no right child for node 2.
- Similarly, the user inputs the value of the right child's left child, which is 5, and then inputs -1 for the right child's right child.
- Finally, the user inputs the value of the right child's right child, which is 6.
Binary Tree Construction:
- Based on the input provided, the binary tree is constructed as follows: markdown 1 /
  2 3 /
  4 6
  5
  
  Inorder Traversal:
  - The inorder traversal of the constructed binary tree is performed recursively.
  - The values are printed in non-decreasing order as 4 2 1 5 3 6, which represents the inorder traversal path from the root node.
Input: Values of Nodes: The user inputs the values of each node in the binary tree. If a node does not have a left or right child, the user enters -1. For example, let's consider the following input: 10 20 30 40 -1 50 -1 -1 60 Output: The output will be the inorder traversal of the constructed binary tree. For the provided input, the output would be: 40 20 50 10 30 60

Explanation: Input Interpretation:
- The user inputs the value of the root node, which is 10.
- Then, the user inputs the values of the left and right children of the root node, which are 20 and 30, respectively.
- Further, the user inputs the values of the left child's left child, which is 40.
- Then, the user inputs the value of the left child's right child, which is -1, indicating that there is no right child for node 20.
- Similarly, the user inputs the value of the right child's left child, which is 50, and then inputs -1 for the right child's right child.
- Finally, the user inputs the value of the right child's right child, which is 60.
Binary Tree Construction:
- Based on the input provided, the binary tree is constructed as follows: 10 /
  20 30 / /
  40 50
  60 Inorder Traversal:
  - The inorder traversal of the constructed binary tree is performed recursively.
  - The values are printed in non-decreasing order as 40 20 50 10 30 60, which represents the inorder traversal path from the root node.

Conclusion

Understanding trees and traversal algorithms, such as inorder traversal, is crucial in computer science. These codes provide a practical example of how to implement and apply inorder traversal in different languages like Python ,C++ and Java. The recursive nature of the traversal allows for elegant and concise code, making it a powerful tool for tree-related operations.