Data Structures: Trees

A Tree is a data structure. Just like in nature they have roots, branches and leaves. The following key terms are associated with tree structures

• Root Node - The node at the very top of the structure
• Children - subsequent nodes below the current node. Children of the root node are subsequently parent nodes of the nodes that follow.
• Braches - The lines that join the nodes are called branches.
• Leaf Nodes - Nodes without sub-trees are called leaf /terminal nodes

Binary Trees

A specific type of tree where each node is only allowed up to two children. In this case, each node contains:

• A Left Pointer
• Data
• A right pointer

Binary trees are often used to convert infix algebraic notation to RPN (reverse polish notation)

Tree Traversals

A tree traversal is the path you take to visit each node in the tree. The following travsersals are depth first traversals. Depth traversals are implemented using a stack:

• Pre Order
• In Order
• Depth Order

It's easy to remember how to traverse, just use the acronym VLR for pre-order, LVR (in order) and LRV (post order). Add the acronym above each node, then, staring at the root node follow the acronym, crossing each letter as you perform the action. (L=Left, R=Right, V=Visit)

Alternatively a breadth first traversal can be used. This checks the tree a level at a time. It is implmented using a queue