Trees are a data structure that like linked lists are made of up of nodes with a data flow that is directed, meaning that data moves down from node to node. Trees are usually have one node at the top with nodes connected to it branching downwards.
Trees can be thought of as an ancestry chart top node is called the root node/ parent node, nodes 2 and 3 are siblings since they have the same parent. Nodes 4 and 5 are children of node 5. Nodes with no children are called leaf nodes. In trees nodes will only ever have one parent node. When traversing a tree depending on the direction the movement has different names, if moving from root down to child we call this depth, if moving from the leaf node up we call this height. The depth or height number lets us know how many nodes are in the tree.
Binary trees have a restriction that a parent node can have no more than two children nodes, these nodes are referred to as the left child and the right child. Left child values have to be less than the parent, and right child values must be bigger than the parent. These rules help search through a binary tree easily.
For an example of a binary search tree traversal using rules mentioned above let’s say we want to find the number 12 in the above tree.
12 < 25 so we move to the left child.
12 < 20 so we move to the left child again.
12 > 10 so we move to the right child
And here we find our value.
In a tree of 12 elements we only had to make 3 moves to locate our value.
