Trees

A tree is our first structure that’s a hierarchical one. Each tree has one root node, and the different trees vary from there. They can be ordered or not. Nodes are referred to as leaves, and the parent-child analogy or ancestry works well here. Leaves with no children are called (). The nodes are connected by edges.

Binary Search Trees — each node can only have two children. They are ordered, the left node has lesser than parent, node to the right is greater than the parent. This has excellent time complexity, since each step you take removes half of the possible remaining choices.