CSE 331: Binary Search Trees

In-order traversal

Left → root → Right

visit node between children 

if node is None:
	return 
inOrder(node.left)
visit(node)
inOrder(node.right)

This will give sorted order. 

Post-Order Traversal

Left → Right → root

visit node after children 

if node is None:
	return
postOrder(node.left)
postOrder(node.right)
visit(node)

Use when deleting a tree. Delete children first.

Pre-Order Traversal

Root → Left → Right

Visit node BEFORE children

if node is None:
	return 
visit(node)
preOrder(node.left)
preOrder(node.right)

Good for copying a tree. 

Level-Order Traversal

level by level → Left to Right

levelOrder(root):
	queue = Queue()
	queue.enqueue(root)
	
	while not queue.is_empty():
		visit(Node)
		if node.left:
			queue.enqueue(node.left)
		if node.right:
			queue.enqueue(node.right)

Finds shortest path, level by level processing. 

Leaf

A tree node with no children

Internal Node

A node with at least one child

Root

The one tree node with no parent (the "top" node). If the root has no children, and therefore is the tree's only node, the root is a leaf. Otherwise the root is an internal node.

Parent

A node with a child that is that child's parent.

A nodes ancestors

include the nodes parent, the parent's parent, etc., up to the tree's root

A nodes descendants

include the node's children, the children's children, etc.

edge

the link from anode to a child

A node's depth

the number of edges on the path from the root to the node.

tree level

what all nodes with the same depth form

Binary Tree Subtree

any node X in the tree, and all of X's descendants.

What are trees commonly used to represent?

Hierarchical data. A tree can represent files and directories in a file system, since a file system is a hierarchy.

Binary Space Partitioning (BSP)

a technique of repeatedly separating a region of space into two parts and cataloging objects contained within the regions

BST Ordering Property

each node's key is > all keys in the node's left subtree and < all keys in the node's right subtree

BST node's successor

the node that comes after in the BST ordering

BST node's predecessor

the node that comes before in the BST ordering

BST worst case

requires H + 1 comparisons, meaning O(H) comparisons, where H is the tree height

A complete tree's height

H = log base 2 of N (+! if. not perfect and in worst case)

How does BSTInsertNode() traverse?

It traverses the tree from the root to a leaf node to find the insertion location.

BSTInsertKey() Best Case

O(log N)

BSTInsertKey() WorstCase

O(N)

BST remove operation

removes the first-found matching node, restructuring the tree to preserve the BST ordering property

Inorder traversal algorithm

visits all nodes in tree once and performs an operation on each node. Visits all nodes in a BST from smallest to largest.

What does postorder traversal do?

adds the keys to keyList after the two recursive calls. Visits all the tree's leaves first and the root last.

What does preorder traversal do?

It matches the insertion order. It can be used to duplicate a BST.