Lab Assignment Report - InOrder Binary Search Tree Traversal

Categories: Chemistry

Report, Pages 3 (630 words)

Views

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:

Create a binary tree data structure.
Implement the InOrder traversal algorithm using recursion.
Fill the binary tree with numeric values (either manually or through user input) to create a valid binary search tree.
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.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:

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

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!

Don't use plagiarized sources. Get your custom paper on

“ Lab Assignment Report – InOrder Binary Search Tree Traversal ”

Get high-quality paper

NEW! smart matching with writer

The output will be:

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.

Doctor Jennifer

Verified writer

Proficient in: Chemistry

5 (893)

“ Thank you so much for accepting my assignment the night before it was due. I look forward to working with you moving forward ”

+84 relevant experts are online

Hire writer

Here's how you can achieve this:

Import the "java.util.Scanner" class to enable user input.
Use the "Scanner" class to read user input for numeric values to populate the binary tree.
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...
}

Lab Assignment Report - InOrder Binary Search Tree Traversal. (2023, Aug 04). Retrieved from https://studymoose.com/document/comp-182-lab-assignment-8-inorder-binary-search-tree-traversal