COMP 182: Lab Assignment 8 - InOrder Binary Search Tree Traversal

import java . util . Scanner ; public class Lab8 { public static void main ( String [] args ) { Scanner stdin = new Scanner ( System . in ); int numOfNodes ; int [] userNums ; System . out . print ( "Enter the number of nodes you want to add to the tree: " ); numOfNodes = stdin . nextInt (); userNums = new int [ numOfNodes ]; System . out . print ( "Enter your numbers separated by space (duplicates will be ignored): " ); for ( int i = 0 ; i < numOfNodes ; i ++) { userNums [ i ] = stdin . nextInt (); } // create the binary tree BinaryTree bt = BinaryTree . create ( userNums ); // traverse the binary tree using recursive InOrder traversal System . out . print ( "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 ; this . left = null ; this . right = null ; } } // root of binary tree TreeNode root ; /** * algorithm to traverse the binary tree on recursive InOrder */ public void inOrder () { inOrder ( root ); } private void inOrder ( TreeNode node ) { if ( node == null ) { return ; } inOrder ( node . left ); System . out . print ( 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 ( int [] userNums ) { BinaryTree tree = new BinaryTree (); //Populate binary tree with user Numbers for ( int i = 0 ; i < userNums . length ; i ++) { insertNode ( tree , new TreeNode ( userNums [ i ])); } return tree ; } public static void insertNode ( BinaryTree tree , TreeNode newNode ) { TreeNode current = tree . root ; //if tree is empty; assign the node to the root if ( current == null ) { tree . root = newNode ; return ; } while ( true ) { //if node is less than the root, insert it to the left side of the tree if ( newNode . data < current . data ) { if ( current . left == null ) { current . left = newNode ; return ; } else current = current . left ; } //if node is greater than the root, insert it to the right side of the tree else if ( newNode . data > current . data ) { if ( current . right == null ) { current . right = newNode ; return ; } else { current = current . right ; } } else { return ; } } } }