Lab Assignment Report - InOrder Binary Search Tree Traversal

Introduction

In this lab assignment, we are tasked with writing a Java program to traverse a binary tree using InOrder traversal with recursion. In InOrder traversal, we visit the left node first, followed by the root, and then the right node. The program should create a binary tree with numeric placeholders (instead of letters) to satisfy the requirements of a valid binary search tree. While user input for numbers is optional, it will result in extra credit points if implemented. This assignment focuses on implementing the InOrder traversal algorithm and creating a binary tree data structure.

Methodology

The assignment involves the following steps:

1. Create a binary tree data structure.
2. Implement the InOrder traversal algorithm using recursion.
3. Fill the binary tree with numeric values (either manually or through user input) to create a valid binary search tree.
4. Print the nodes of the binary tree in the order they are visited during the InOrder traversal.

Code Implementation

Below is the Java code for implementing the InOrder traversal of a binary tree:

import java.util.Stack;

public class Lab8 {
public static void main(String[] args) {

    // Create the binary tree
    BinaryTree bt = BinaryTree.create();

    // Traverse the binary tree using recursive InOrder traversal
    System.out.println("Nodes of binary tree on recursive InOrder traversal:");

    bt.inOrder();
}
}

class BinaryTree {
static class TreeNode {
int data;
TreeNode left;
TreeNode right;
    TreeNode(int value) {
        this.data = value;
        left = right = null;
    }
}

// Root of binary tree
TreeNode root;

/**
 * Algorithm to traverse the binary tree using recursive InOrder traversal
 */
public void inOrder() {
    inOrder(root);
}

private void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.

	

		Get to Know The Price Estimate For Your Paper
	
	

		

			Topic
			
		
	
	

		

			
				Deadline: 10 days left
				

					
					
				
			
		
	
	

		

			Number of pages
			

				
					
				
				
				
					
				
			
		
	
	

		

			Email
			
			Invalid email
		
	
	

		

			
				
				
			
			

				By clicking “Check Writers’ Offers”, you agree to our terms of service and privacy policy. We’ll occasionally send you promo and account related email
			
		
		
"You must agree to out terms of services and privacy policy"
	
	

		Write my paper
        
You won’t be charged yet!
	

left);
        System.out.println(node.data);
        inOrder(node.right);
    }
}

/**
 * Java method to create binary tree with test data
 *
 * @return a sample binary tree for testing
 */
public static BinaryTree create() {
    BinaryTree tree = new BinaryTree();
    TreeNode root = new TreeNode(4);

    tree.root = root;

    root.left = new TreeNode(2);
    root.right = new TreeNode(6);
    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(3);
    root.right.left = new TreeNode(5);
    root.right.right = new TreeNode(7);

    return tree;
}
}

Results

Upon running the provided Java program, it will create a binary tree with the following structure:

    4
   / \
  2   6
 / \ / \
1  3 5  7

Then, it will perform an InOrder traversal of the binary tree and print the nodes in the order they are visited. The output will be:

1
2
3
4
5
6
7

The program successfully demonstrates the InOrder traversal of a binary search tree.

Optional User Input (Extra Credit)

If you want to implement user input for filling the binary tree with numbers, you can modify the code to prompt the user for input. Here's how you can achieve this:

1. Import the "java.util.Scanner" class to enable user input.
2. Use the "Scanner" class to read user input for numeric values to populate the binary tree.
3. Replace the manually assigned values in the "create" method with user-inputted values.

By implementing these changes, your program can ask the user to input numbers and sort them into a binary tree, resulting in a valid binary search tree. This modification will earn you 5 extra credit points, making the assignment worth up to 200%.

Conclusion

This lab assignment has provided hands-on experience in working with binary trees and implementing the InOrder traversal algorithm using recursion. It demonstrates how to create a binary tree data structure and traverse it in a specific order. Additionally, it highlights the flexibility of the code by allowing for user input to create a binary search tree.

Appendix

Below are the Java classes used in this assignment:

Lab8.java

import java.util.Stack;

public class Lab8 {
public static void main(String[] args) {
    // ... (Refer to the Methodology section for the complete code)
}
}

BinaryTree.java

class BinaryTree {
static class TreeNode {
int data;
TreeNode left;
TreeNode right;
    TreeNode(int value) {
        this.data = value;
        left = right = null;
    }
}

// Root of binary tree
TreeNode root;

// Methods for creating the binary tree and performing InOrder traversal...
}