Binary Search Tree

AlgorithmsCodingDataStructuresGraphTheory A binary search tree or (BST) is a tree such that each node has at most two children and satisfies

left descendents <= n < right descendents 

A balanced binary tree is one that is “balanced enough” to ensure efficient access:

Complexity:

Insert: O(log n) (balanced)
		O(n)     (worst case)
Remove: O(log n) (balanced)
		O(n)     (worst case)
Access: O(log n) (balanced)
		O(n)     (worst case)

Traversal:

1. In-order: (ascending)

def inOrder(root):
	if root != None:
		inOrder(root.left)
		f(root)
		inOrder(root.right)

2. Pre-order: (Root visited first)

def preOrder(root):
	if root != None:
		f(root)
		inOrder(root.left)
		inOrder(root.right)

3. Post-order: (Root visited last)

def inOrder(root):
	if root != None:
		inOrder(root.left)
		inOrder(root.right)
		f(root)