The Binary Search Tree Functions Set

BinarySearchTreeUtils.java

package com.frank.binarysearchtree;

import java.util.LinkedList;

public class BinarySearchTreeUtils {

	public static TreeNode binarySearchTree(TreeNode root, int target) {
		TreeNode node = root;
		while (node != null) {
			if (node.val < target) {
				node = node.right;
			} else if (node.val > target) {
				node = node.left;
			} else {
				return node;
			}
		}
		return null;
	}

	public static void insertNode(TreeNode root, TreeNode newNode) {
		if (root == null) {
			root = newNode;
			return;
		}
		TreeNode tempNode = root;
		while (tempNode != null) {
			if (tempNode.val > newNode.val) {
				if (tempNode.left == null) {
					tempNode.left = newNode;
					return;
				}
				tempNode = tempNode.left;
			} else {
				if (tempNode.right == null) {
					tempNode.right = newNode;
					return;
				}
				tempNode = tempNode.right;
			}
		}
	}

	// Delete Node
	public static void deleteNode(TreeNode root, TreeNode deleteNode) {
		TreeNode tempNode = root;
		TreeNode parentTempNode = null;
		while(tempNode != null && tempNode.val != deleteNode.val) {
			parentTempNode = tempNode;
			if (deleteNode.val > tempNode.val) {
				tempNode = tempNode.right;
			} else {
				tempNode = tempNode.left;
			}
		}
		
		// If not found
		if (tempNode == null) {
			return;
		}
		
		// If tempNode has left and right child
		if (tempNode.left != null && tempNode.right != null) {
			TreeNode minTreeNode = tempNode.right;
			TreeNode parentMinTreeNode = minTreeNode;
			while(minTreeNode.left != null) {
				parentMinTreeNode = minTreeNode;
				minTreeNode = minTreeNode.left;
			}
			tempNode.val = minTreeNode.val;
			tempNode = minTreeNode;
			parentTempNode = parentMinTreeNode;
		}
		
		// Delete Leaf Node or Only One child
		TreeNode child;
		if (tempNode.left != null) {
			child = tempNode.left;
		} else if (tempNode.right != null) {
			child = tempNode.right;
		} else {
			child = null;
		}
		
		// Delete Root node
		if (parentTempNode == null) {
			root = child;
		} else if (parentTempNode.left == tempNode) {
			parentTempNode.left = child;
		} else {
			parentTempNode.right = child;
		}
	}
	
	// Find the largest number in the tree
	public  static int findMaxValue(TreeNode root) {
		TreeNode tempNode = root;
		while(tempNode.right != null) {
			tempNode = tempNode.right;
		}
		return tempNode.val;
	}
	
	public static int findMinValue(TreeNode root) {
		TreeNode tempNode = root;
		while(tempNode.left != null) {
			tempNode = tempNode.left;
		}
		return tempNode.val;
	}
	
	public static void preOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.val + " ");
		preOrder(root.left);
		preOrder(root.right);
	}
	
	public static void inOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		inOrder(root.left);
		System.out.print(root.val + " ");
		inOrder(root.right);
	}
	
	public static void postOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		postOrder(root.left);
		postOrder(root.right);
		System.out.print(root.val + " ");
	}
	
	public static void levelOrder(TreeNode root) {
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while(!queue.isEmpty()) {
			TreeNode tempNode = queue.poll();
			System.out.print(tempNode.val + " ");
			if (tempNode.left != null) {
				queue.add(tempNode.left);
			}
			if (tempNode.right != null) {
				queue.add(tempNode.right);
			}
		}
	}
}