02 Tree Traversal

DeleThere are four ways to traverse a tree:

Level Traversal → Visit nodes on each level
Pre-Order Traversal → Visit the root of every subtree first.
Post-Order Traversal → Visit the root of every subtree last.
In-order Traversal → Visit left child, then root and then right.

Level Traversal

And for the level traversal we start at level zero and then we move to level one and we move from left to right, and then we go to level two and we move from left to right, and we go to three and we move from left to right. So we visit 25, then 20 and 27, then 15, 22, 26 and 30 and then 29 and 32.

Pre-Order Traversal

For pre-order traversal we always visit the subtree first.

And so we're gonna start at 25 and then we're going to go to 20, and then we go to 15. 15 doesn't have any children and so we go back up to the root which we've already visited and we visit 22. So the order so far is 25, 20, 15, 22 and then we go back up, we visit 27 and then 26, we go back to the root and visit 30 and then 29 and then 32.

In-Order Traversal

We visit the left side and then we visit the root and then we completely visit the right side.

So with in-order, it's always do the entire left side then the root, then the entire right side for every node. And so it's 15, 20, 22, 25, 26, 'cause we need to do the left side first, 27, 29, because we do the left side first, 30 and 32.

Now notice something here, the data is sorted, 15, 20, 22, 25, 26, 27, 29, 30 and 32, and that's why it's called in-order.

And so because of the characteristics of a binary search tree, if we do an in-order traversal the data is sorted.

Post Order Traversal

Root goes last, you will visit the entire left subtree for a node and then the entire right subtree for the node and finally you hit the node.

Delete

When we are dealing with a binary search tree, meaning that nodes can have zero, one or two children, there are 3 possibilities.

First is the node we want to delete is a leaf.
Second is that the node we want to delete has one child.
Third is the node that we want to delete that has two children.

Delete Node with 2 Children

Need to figure out what the replacement node will be (When a node has 2 children, we are going to replace that node with one of the nodes from it’s subtrees.)
Want minimal distribution to existing tree structure
Can take the replacement node from the deleted node’s left subtree or right subtree.
if taking it from the right subtree, we have to take the smallest value in the right subtree.
If taking it from the left subtree, we have to take the largest value in the left subtree
Choose one and stick with it.

Exercise

Insert 28