5.1.17

Sketch binary trees.

Teaching Note:

Students should be able to sketch diagrams showing the resulting binary tree after adding a new data item, adding one or more new nodes, and/or removing one or more nodes.

Sample Question:

sdfsdfsf

JSR Notes:

Here's a video of it all, followed by individual diagrams.

(And the other way to say this, in terms of coding algorithms is: "link 'previous' to what it 'current_to_delete' is pointing to.)

--> But note here that the smallest in the right sub-tree could have a child or subtree too the right, so it's parent will have to be re-linked to it's right child/subtree.

Two children removal - B

(And one other point is that it also works to move the largest of its left sub-tree to replace the target node.)

(Old screen shots of the video; re-done in Illustrator, above. Kept for reference for now.)

Adding a node to a tree.

Adding A Node to a Tree

Tree removeal if no children

Removing a Node which has No Children

ONe child

Removing a Node which has One Child

Two children

Removing a Node which has Two Children