Binary Tree Traversal

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( );


 }
}

 

 

Advertisement