Blog Details

Binary Search Tree (BST)

1. Powerful BST

Binary search tree, sometimes called ordered or sorted binary trees, are a particular type of container that store “items” in memory.

This allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key.

2. Let’s see the real thing


The properties of Binary Search Tree:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.

3. PreOrder Traversal

preOrder(r) = print(r) -> preOrder(r.left) -> preOrder(r.right);
public static void preOrder(TreeNode root) {
	if (root == null) {
		return;
	}
	System.out.print(root.val + " ");
	preOrder(root.left);
	preOrder(root.right);
}

It visits the node first, and visit the left node, and lastly, the right node.

4. InOrder Traversal

inOrder(r) = inOrder(r.left) -> print(r) -> inOrder(r.right)
public static void inOrder(TreeNode root) {
	if (root == null) {
		return;
	}
	inOrder(root.left);
	System.out.print(root.val + " ");
	inOrder(root.right);
}

It visit the left (small) node first, then the node itself, and lastly, the right node.

By doing this, it will return the ordered tree nodes by ascending way. Here it is:

13 16 17 18 19 25 27 33 34 50 51 58 66 

5. PostOrder Traversal

postOrder(r) = postOrder(r.left)-> postOrder(r.right) -> print(r)
public static void postOrder(TreeNode root) {
	if (root == null) {
		return;
	}
	postOrder(root.left);
	postOrder(root.right);
	System.out.print(root.val + " ");
}

6. LevelOrder Traversal

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

To print the Tree nodes, level by level.

7. Find Max Value in the BST

public  static int findMaxValue(TreeNode root) {
	TreeNode tempNode = root;
	while(tempNode.right != null) {
		tempNode = tempNode.right;
	}
	return tempNode.val;
}

To find the max value, all the way go down to the right subtree, and till to the end, it is the max value.

8. Find Min Value in the BST

public static int findMinValue(TreeNode root) {
	TreeNode tempNode = root;
	while(tempNode.left != null) {
		tempNode = tempNode.left;
	}
	return tempNode.val;
}

9. Find the target value in the BST

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;
}

10. Insert a new Node to the BST

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;
		}
	}
}

Compare the value first, then find the right place to add new node to the BST.

11. Delete the node from the BST

// 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;
	}
}

Several cases in the deletion:

  • If no child nodes, we just set its parent node to null.
  • If only one child node, we update its parent node to the child node.
  • If has two nodes, we need to find the smallest node from the right node, and update it with the smallest node.

Here you can find the complete source code of this article:

https://gist.github.com/darkcar/22c6a93b63d2c8835bd7b33aa0fc47b5