Trees are called Binary Trees based on how they’re structured. Every binary tree contains two subtrees within it, which are a right subtree and a left subtree. These are simply trees that follow a certain set of rules and make searching for items within it easier. This can be seen when trying to use operations such as insert() or delete().

Image from Tamara Nelson-Fromm

Organization and Traversal

As you can see in the picture above, the root number is the one on the very top, and all the numbers smaller than the root are in the left subtree, and all the numbers greater than the root are on the right subtree. If we wanted to insert 3 using what is known as in-order traversal, for example, we compare it with the root node 4, and since its smaller, it goes to the left subtree. Since 3 is greater than 2, it goes to the right child of node 2. Perfect binary trees are trees in which all leaves are on the same level. The prefix to the name of a traversal lets us know when we visit the node that we are currently at. When traversing, it checks if the right of the node exists and if it doesn’t, it goes back to its caller, and then instead of visiting its left, it visits its right. Below is the pseudocode for the insert operation.

Insert:
If the node has space:
If there is no right node, then add a new_node and return.
else, recursively call insert to keep traversing tree if there is no space
If the new_node data is less than the data of the node:
If node.left has space, insert a new node and return.
else, recursively call insert to keep traversing tree if there is no space

Recursion

One of the main points of post-order, pre-order and in-order traversals are that you call the function again repeatedly to continue to insert other elements. This is also the case for the insert operation, where if the node is occupied, it will keep looking and recursively calling the insert function. Since the function will continue to perform the same operation, it will keep calling the same sets of instructions that visit each node and will stop when the base case is reached. In-order traverses left subtree, node, right subtree, and post-order traversal is left subtree, right subtree, node. An example of pre-order traversal is the function checking if the right of the node exists and if it doesn’t, it goes back to its caller, and then instead of visiting its left, it visits its right. It takes practice, and drawing out the tree diagrams helps in understanding.