CSC 230 (4) - Binary Search Trees (BST)

What is a Binary Search Tree (BST)?

A tree in which each node has at most two children, the left child and the right child.

What are the main parts of a BST?

Root, leaves, and internal nodes.

What properties of a BST should be understood?

Tree height, tree diameter, node level, node parent, node children, perfect tree, full tree, complete tree.

What is a perfect tree?

A tree where all internal nodes have two children and all leaves are at the same level

What is a full tree?

A tree where every node has either 0 or 2 children.

What is a complete tree?

A tree that is completely filled on all levels except possibly the last, which is filled from left to right.

How do you determine if a tree is a valid BST?

For any node, all left children are ordered to the left of the parent, and all right children are ordered to the right of the parent.

What is Level-order Traversal?

Traversing nodes level by level, from top to bottom; iterative version uses two queues

What is In-order Traversal?

Traverse left subtree, visit node, traverse right subtree; recursive version recurses left, visits node, recurses right; iterative version uses a stack.

What is Pre-order Traversal?

Visit node, traverse left subtree, traverse right subtree; usually recursive.

What is Post-order Traversal?

Traverse left subtree, traverse right subtree, visit node; usually recursive.

What algorithms are important for BSTs?

BST Search, BST Insert, BST Remove (Delete).

How do you perform insertion in a BST?

Compare the value to the current node; go left if smaller, right if larger; insert at the appropriate null child position.

How do you perform deletion from a BST?

There are three cases:

• Node is a leaf → delete directly

• Node has one child → delete node and move child up

• Node has two children → replace node with in-order successor (or predecessor) and recursively remove successor (or predecessor)

What is an in-order successor in a BST?

The smallest node in the right subtree of the node being deleted.

What is an in-order predecessor in a BST?

The largest node in the left subtree of the node being deleted.

When deleting a node with two children, why do we use the in-order successor or predecessor?

To maintain the BST property that all left children are smaller and all right children are larger.

What data structures are used in iterative BST traversals?

Stack for in-order traversal; queues for level-order traversal.

Summary: recursive orders of traversal

• In-order → left, node, right

• Pre-order → node, left, right

• Post-order → left, right, node

Next, do problem set 08 and then do quiz 09