Binary Trees and Binary Search Trees

Common Terminology

• Node - A node is the individual item/data that makes up the data structure
• Root - The root is the first/top Node in the tree
• Left Child - The node that is positioned to the left of a root or node
• Right Child - The node that is positioned to the right of a root or node
• Edge - The edge in a tree is the link between a parent and child node
• Leaf - A leaf is a node that does not contain any children
• Height - The height of a tree is determined by the number of edges from the root to the bottommost node

There are two categories of traversals when it comes to trees:

• Depth First
• Breadth First

Depth First

Depth first traversal is where we prioritize going through the depth (height) of the tree first. There are multiple ways to carry out depth first traversal, and each method changes the order in which we search/print the root. Here are three methods for depth first traversal:

• Pre-order: root >> left >> right
• In-order: left >> root >> right
• Post-order: left >> right >> root

Given the sample tree above, our traversals would result in different paths:

• Pre-order: A, B, D, E, C, F
• In-order: D, B, E, A, F, C
• Post-order: D, E, B, F, C, A