public class BinarySearchTree { * Root node of the binary search tree. */ private Node root; /** * Internal static class for storing the nodes. */ private static class Node { Node parent; Node left; Node right; int data; Node( int data ) { this.data = data; } public String toString( ) { // no use of this method in this program return "" + data; } } /** * Inserts a new node that has the specified data. The insert starts from * the root of the tree and goes all the way down until it finds a spot to * place the new node. */ public void insert( int data ) { root = insert( root, data ); } /** * Inserts a new node that has the specified data. The insert starts from * the specified node of the tree and goes all the way down until it finds * a spot to place the new node. */ public Node insert( Node node, int data ) { if( node == null ) { // Found a spot to insert new node. node = new Node( data ); } else if( data < node.data ) { // Insert in left subtree node.left = insert( node.left, data ); node.left.parent = node; } else { // Insert right subtree. node.right = insert( node.right, data ); node.right.parent = node; } // Done! return node; } /** * Helper method for the binary search tree delete operation. It used for * swapping the nodes, while keeping the structure of the binary search tree. * Refer to page 296 of Introduction to Algorithms (3rd Edition) by Cormen * et. al. for further details. */ private void swap( Node a, Node b ) { if( a.parent == null ) { root = b; } else if( a == a.parent.left ) { a.parent.left = b; } else { a.parent.right = b; } if( b != null ) { b.parent = a.parent; } } /** * Deletes the node containing the specified data. The search for the node * to be deleted starts from the root node. */ public void delete( int data ) { delete( root, data ); } /** * Deletes the node containing the specified data. The search for the node * to be deleted starts from the specified node. Refer to page 298 of * Introduction to Algorithms (3rd Edition) by Cormen et. al. for further * details. */ public void delete( Node node, int data ) { // Can't find the node we want to delete. if( node == null ) { return; } // We've found the node we want to delete. else if ( data == node.data) { // Check if it has a left subtree. If it deson't then just replace // the node we want to delete with its right subtree. if( node.left == null ) { swap( node, node.right ); } // Check if it has a right subtree. If it doesn't then just replace // the node we want to delete with its left subtree. else if( node.right == null ) { swap( node, node.left ); } // Since it has both a left and right subtree, then traverse to the // left-most child of the right subtree (i.e. the smallest node in the // right subtree). Once found, exchange the data values between the node // and the node that we want to delete. else { Node minNode = node.right; while( minNode.left != null ) { minNode = minNode.left; } if( minNode.parent != node ) { swap( minNode, minNode.right ); minNode.right = node.right; minNode.right.parent = minNode; } swap( node, minNode ); minNode.left = node.left; minNode.left.parent = minNode; } } // Continue searching in the left subtree. else if( data < node.data) { delete( node.left, data ); } // Continue searching in the right subtree. else { delete( node.right, data ); } } /** * Returns a boolean true if it finds the specified data in the tree, or false * otherwise. The search starts from the root node of the tree. */ public boolean lookup( int data ) { return lookup( root, data ); } /** * Returns a boolean true if it finds the specified data in the tree, or false * otherwise. The search starts from the specified node of the tree. Thus, you * can either search the whole tree or a subtree. */ public boolean lookup( Node node, int data ) { if( node == null ) { // Can't find it. return false; } else if( data == node.data) { // Found it. return true; } else if( data < node.data) { // Search left subtree. return lookup( node.left, data ); } else { // Search right subtree. return lookup( node.right, data ); } } public int countLeaves() { return countLeaves(root); } public int countLeaves(Node node) { // Return the number of leaves in the tree to which node points. if (node == null) return 0; else if (node.left == null && node.right == null) return 1; // Node is a leaf. else return countLeaves(node.left) + countLeaves(node.right); } /** * Returns the size of the tree via an in-order traversal, starting from * the root node. */ public int size( ) { return size( root ); } /** * Returns the size of the tree via an in-order traversal, starting from * the specified node. */ public int size( Node node ) { if( node == null ) { // We've reached the bottom. return 0; } int leftSize = size( node.left ); int rightSize = size( node.right ); // Add 1 to account for the size of the current node. return leftSize +rightSize+ 1; } /** * Returns the max root-to-leaf depth of the tree. */ public int maxDepth( ) { return maxDepth( root ); } /** * Returns the max node-to-leaf depth of the tree. */ public int maxDepth( Node node ) { if( node == null ) { // We've reached the bottom. return 0; } int leftDepth = maxDepth( node.left ); int rightDepth = maxDepth( node.right ); // Add 1 to the largest depth, to account for the depth of the current node. return leftDepth < rightDepth ? rightDepth + 1 : leftDepth + 1; } /** * Returns the min value starting from the root node. */ public int minValue( ) { return minValue( root ); } /** * Returns the min value starting from the specified node. */ public int minValue( Node node ) { // Traverse to the left-most child, as it has the min value. Node cursor = node; while( cursor.left != null ) { cursor = cursor.left; } // Return the value of the left-most child. return cursor.data; } /** * Returns the max value starting from the root node. */ public int maxValue( ) { return maxValue( root ); } /** * Returns the max value starting from the specified node. */ public int maxValue( Node node ) { // Traverse to the right-most child, as it has the max value. Node cursor = node; while( cursor.right != null ) { cursor = cursor.right; } // Return the value of the right-most child. return cursor.data; } /** * Traverses the tree in a pre-order approach, starting from the root node. */ public void preorderTraversal( ) { preorderTraversal( root ); } /** * Traverses the tree in a pre-order approach, starting from the specified node. */ public void preorderTraversal( Node node ) { if( node != null ) { System.out.print( node.data + " " ); preorderTraversal( node.left ); preorderTraversal( node.right ); } } /** * Traverses the tree in a in-order approach, starting from the root node. */ public void inorderTraversal( ) { inorderTraversal( root ); } /** * Traverses the tree in a in-order approach, starting from the specified node. */ private void inorderTraversal( Node node ) { if( node != null ) { inorderTraversal( node.left ); System.out.print( node.data + " " ); inorderTraversal( node.right ); } } /** * Traverses the tree in a post-order approach, starting from the root node. */ public void postorderTraversal( ) { postorderTraversal( root ); } /** * Traverses the tree in a post-order approach, starting from the specified node. */ public void postorderTraversal( Node node ) { if( node != null ) { postorderTraversal( node.left ); postorderTraversal( node.right ); System.out.print( node.data + " " ); } } /** * Test Method */ public static void main( String[ ] args ) { BinarySearchTree bst = new BinarySearchTree( ); int[ ] input = new int[ ] { 15,6,18,3,7,17,20,2,4,13,9 }; for( int i : input ) { bst.insert( i ); } System.out.println( "Preorder Traversal:" ); bst.preorderTraversal( ); System.out.println( "\nInorder Traversal:" ); bst.inorderTraversal( ); System.out.println( "\n Size(Elements) of the tree is:"+bst.size() ); System.out.println( " Height of tree is :" +bst.maxDepth() ); System.out.println( "Min Value in the tree is :" +bst.minValue() ); System.out.println( " Max Value in the tree is :" +bst.maxValue() ); System.out.println( " Lookup(node present in tree ) :" +bst.lookup(70) ); System.out.println( " Lookup(node present in tree ) :" +bst.lookup(13) ); int leafCount = bst.countLeaves(); System.out.println("Number of leaves: " + leafCount); System.out.println( "\nPostorder Traversal:" ); bst.postorderTraversal( ); bst.delete( 3 ); bst.delete( 7 ); bst.delete( 20 ); System.out.println( "\n \nPreorder Traversal:" ); bst.preorderTraversal( ); System.out.println( "\nInorder Traversal:" ); bst.inorderTraversal( ); System.out.println( "\n Size(Elements) in the tree are :"+bst.size() ); System.out.println( " Height of tree is :" +bst.maxDepth() ); System.out.println( "Min Value in the tree is :" +bst.minValue() ); System.out.println( " Max Value in the tree is :" +bst.maxValue() ); int leafCoun = bst.countLeaves(); System.out.println("Number of leaves: " + leafCoun); System.out.println( "\nPostorder Traversal:" ); bst.postorderTraversal( ); } }