Reading 15

Anatomy of a Binary Tree

A binary tree is a collection of nodes organized in branching child nodes. The max number of children a node can have is determined by the value of K. In binary trees, this value is k=2. The final nodes containing no children are known as leaf nodes.

As you can see in the above image, the root node has two children, a left and right child. Those children each may have a left and right child as well. The connection between each node is called an edge.

Traversal of a Tree

Two methods may be used when traversing a tree:

• Depth First
• Breadth First

Let’s Examine the Depth First Method (Stack Method)

Within the depth method, three different orders may be taken when stepping through the nodes, as seen here:

• Pre-order: root » left » right (Order: A, B, C, D, E, F)
• In-order: left » root » right (Order: D, B, E, A, F, C)
• Post-order: left » right » root (D, E, B, F, C, A)