BST

Complete

Succeeds: trees

Summary

Binary search tree(BST)

implements table

Operation	Method	Performance
`search(v)`	tree traversal	-
`insert(v)`	tree traversal	-
`remove(v)`	tree traversal	-

implements priority queue
acts as both a max and min heap simultaneously

Operation	Method	Performance
`insert(v)`	insert into the tree	-
`extractMax()`/`extractMin()`	remove max/min, rebalance	-

Inorder traversal

left -> self -> right
flattening into a sorted array
BST sort

java

void inOrder(TreeNode node) {
	if (node == null) return;
	inOrder(node.left);
	// visit the current node
	inOrder(node.right);
}

Preorder traversal

self -> left -> right

java

void preOrder(TreeNode node) {
	if (node == null) return;
	// visit the current node
	preOrder(node.left);
	preOrder(node.right);
}

Postorder traversal

left -> right -> self

java

void postOrder(TreeNode node) {
	if (node == null) return;
	postOrder(node.left);
	postOrder(node.right);
	// visit the current node
}

Concept

Abstraction

BST property
- nodes on the left are strictly smaller than the root
- nodes on the right are strictly larger than the root
- 3 high BST

VisuAlgo’s implementation has support for duplicates by storing the count alongside the value

Data structure

pointer to the right and left children
(sometimes) pointer to the parent

java

class TreeNode {
	Object data;
	TreeNode left;
	TreeNode right;
}

Catalan number

number of unique (unbalanced) tree structures with nodes

Max/min

max is the rightmost node
min is the leftmost node
BSTs can act as both a max and min heap simultaneously

Successor/predecessor

with child: successor(6)
min (leftmost) of right subtree

no children: successor(17)
find the parent of the left subtree that the node is in

Removal

no children: remove(8)
simple deletion

one child: remove(19)
child takes over

two children: remove(11)
replace with successor/predecessor

conventionally using the successor

Formal definition of height

Tall trees

this makes (unbalanced) BSTs not more useful than a linear data structure

Application

Leetcode: Search in a Binary Search Tree

java

public TreeNode searchBST(TreeNode root, int val) {
	if (root == null)
		return null;
	if (root.val == val)
		return root;
	else if (root.val > val)
		return searchBST(root.left, val);
	else
		return searchBST(root.right, val);
}

Leetcode: Minimum Absolute Difference in BST

inorder traversal

java

int prev = -1, min = Integer.MAX_VALUE;

public void inOrder(TreeNode root) {
	if (root == null) return;
	inOrder(root.left);
	
	// visit the current node
	if (prev != -1) 
		min = Math.min(min, root.val - prev);
	prev = root.val;
	
	inOrder(root.right);
}

public int getMinimumDifference(TreeNode root) {
	inOrder(root);
	return min;
}

Leetcode: Construct Binary Tree from Preorder and Inorder Traversal

build the tree using preorder traversal
for each subtree, slice the inorder array to build its left and right subtrees

java

int i = 0;
Map<Integer, Integer> mp = new HashMap<>();
int[] pre;

public TreeNode build(int s, int e) {
	if (s > e)
		return null;
	
	int val = pre[i++];
	TreeNode root = new TreeNode(val);

	int idx = mp.get(val);
	root.left = build(s, idx - 1);
	root.right = build(idx + 1, e);
	
	return root;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
	pre = preorder;
	for (int i = 0; i < inorder.length; i++)
		mp.put(inorder[i], i);

	return build(0, inorder.length - 1);
}

Leetcode: Delete Node in a BST

java

public TreeNode deleteNode(TreeNode root, int key) {
	if (root == null)
		return null;
	if (root.val == key) { // found the target
		if (root.left == null && root.right == null) // if no children, just delete it
			return null;
		else if (root.left != null && root.right == null) // has left child only
			return root.left;
		else if (root.left == null && root.right != null) // has right child only
			return root.right;
		else {
			TreeNode succ = root.right; // find the successor of the current node, predecessor will work too
			while (succ.left != null) 
				succ = succ.left;
			root.val = succ.val; // replace the current value with the successor
			root.right = deleteNode(root.right, succ.val); // delete the successor recursively
			return root;
		}
	} else if (root.val > key) {
		root.left = deleteNode(root.left, key);
		return root;
	} else {
		root.right = deleteNode(root.right, key);
		return root;
	}
}