algorithm to remove element from an array

This can be achieved in many ways, some of them are discussed here
– standard way when existing order is important: traverse through the elements, once element_to_be_deleted is found, shift remaining elements one position towards left. The complexity of this algorithm is O(n)
– when order of array is not important: take two pointers; one at the beginning of array and another at the end of the array. Increment the starting pointer till the element_to_be_deleted is found and decrement the ending pointer till element is not equals to element_to_be_deleted and then swap elements at start_pointer and end_pointer. The complexity of this algorithm is O(n)
– brute force algorithm. The complexity of this algorithm is O(n*n)

standard way when existing order is important @ O(n)

	public int removeNumber(int[] a, int n) {

		if (a == null || a.length == 0) 
			return -1;
		int i = 0;
		for (int j=0; j<a.length; j++)
			if (a[j] != n) 
				a[i++] = a[j];
		
		System.out.println("New size of the array is "+i);
		return i; // The new dimension of the array
	}

when order of array is not important @ O(n)

	public void removeElementO_n(int[] a, int element) {
		int startPtr = 0; 
		int endPtr = a.length-1;
		//{1,4,2,4,3,5,4,4};
		while(startPtr < endPtr) {
			while(endPtr > 0 && a[endPtr] == element) {
				a[endPtr]=-1;
				endPtr--;
			}
                        
			while(startPtr < a.length && a[startPtr] != element) {
				startPtr++;
			}
			
			if(startPtr < endPtr) {
				a[startPtr] = a[endPtr];
				a[endPtr] = -1;
				startPtr++;
				endPtr--;
			}
		}
	}

brute force algorithm @ O(n*n)

public void removeElementO_n2(int[] a, int element) {
		int ct=0;
		int ln = a.length;
		//{1,4,2,4,3,5,4,4};
		for (int i = 0; i < a.length; i++) {
			if(a[i] == element) {
				ct++;
				for (int j = i; j < a.length; j++) {
					if((j+1)<a.length) {
						a[j] = a[j+1];
					}
				}
				a[ln-ct] = -1;
			}
		}	
	}

print level wise nodes in the binary tree (Breadth First Traversal)

This can be achieved using breadth first traversal algorithm.
– push level wise nodes into the queue at every iteration
– pop the node from queue at every iteration and print its value

Lets look at example:

            20
    15              25
12      18      22      28

BFS puts this tree in queue such there level wise nodes are placed one-another like this

	--------------------------------
	20 | 15 | 25 | 12 | 18 | 22 | 28
	--------------------------------

And at every loop element from queue is removed in FIFO manner

	public void breadthFirstNonRecursive() {
		Queue<BinaryNode> queue = new java.util.LinkedList<BinaryNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			BinaryNode node = queue.poll();
			System.out.println(node.element);
			if (node.left != null)
				queue.offer(node.left);
			if (node.right != null)
				queue.offer(node.right);
		}
	}

Output: 20, 15, 25, 12, 18, 22, 28

find depth of binary search tree

We can find the depth of the binary search tree in three different recursive ways
– using instance variables to record current depth and total depth at every level
– without using instance variables in top-bottom approach
– without using instance variables in bottom-up approach

Full source code can be downloaded here
Approach #1: using instance variables to record current depth and total depth at every level

	int currentDepth, depth;
	public int depth(BinaryNode n) {
		if (n != null) {
			currentDepth++;
			
			// record total depth if current depth is greater than total depth 
			if (currentDepth > depth) {
				depth = currentDepth;
			}

			// recursively traverse entire tree
			depth(n.left);
			depth(n.right);
			
			// decrement as we traverse up the binary tree
			currentDepth--;
		}
		return depth;
	}

Pros: Easier to implement and understand
Cons: Usage of instance variables. Ideally any recursive call should not make use of instance variables and by doing so it moves close towards linear programming.

Approach #2: without using instance variables in top-bottom approach

	public int depth3(BinaryNode node, int d){
		int leftDepth = d, rightDepth = d;
		
		if(node.left != null){
			leftDepth = depth3(node.left, d+1);
		}
		if(node.right != null){
			rightDepth = depth3(node.right, d+1);
		}
		
		return leftDepth > rightDepth ? leftDepth : rightDepth;
	}
	

Approach #3: without using instance variables in bottom-up approach

	public int depth2(BinaryNode node){
		if(node == null)
			return 0;
		int left = depth2(node.left);
		int right = depth2(node.right);
		
		int x = left > right ? left+1 : right+1;
		return x;
	}

Approach #2 and #3 are actually recursive way of finding the depth. In #2 we only depend on the return type of the method because back-tracking helps us to keep track of the tree depth. In #3, since we are incrementing the depth in top-bottom fashion, we need additional parameter to the method to track the depth.

My 2 cents for best approach is #2.

Full source code can be downloaded here

Output:

Maximum depth of the Binary Tree is using instance variables: 3
Maximum depth of the Binary Tree is without using instance variables in bottom-up approach: 3
Maximum depth of the Binary Tree is without using instance variables in top-bottom approach: 3
|	|-------28
|-------25
|	|-------22
20
|	|-------18
|-------15
|	|-------12