3.2.5 Binary Trees and Binary Tree Traversals

3.2.5 Binary Trees and Binary Tree Traversals

Binary Trees

A Binary Tree is a graph with a

Root Node whose Left Pointer points to the Left Sub-Tree and whose Right Pointer points to the Right Sub-Tree where each Sub-Tree is a Binary Tree.

    This is a   Recursive   Definition

Why Binary Trees?

Much like with Linked Lists, Binary Trees can store data in an ordered format without the need for time consuming moving of data.

They also speed up the process of searching a database.

Breadth-First and Depth-First Traversals

There are different ways of searching or extracting data from Binary Trees.  These split into two main types...

•       Breath-First Traversals

•       Depth-First Traversals

Breadth-First Traversal

Start with the Root Node and visit each of its Child Nodes

Take each of those Nodes and visit each of its child nodes

And so on...

Depth-First Traversal

There are three types of Depth-First Traversal

•       In-Order Traversal

Left-Tree, Root, Right Tree

•       Pre-Order Traversal

Root, Left-Tree, Right Tree

•       Post-Order Traversal

Left-Tree, Right-Tree, Root