Trees

Just like an ordinary tree you see, but the inverted version. Root goes on the top. This is a common phrase you hear when tree is being introduced.

Unlike arrays and stacks, tree is a hierarchical data structure. This clearly means that there is a notion of parent and children. And even grandparents of course. Root of the tree has no parent and the leaves have no children yet. Nodes that are not leaves are called internal nodes, having at least one child.

Now the trees which can be related to the olden days, called general trees have no restrictions on the number of children. But there are “n-ary trees” which can have at most ‘n’ children. The very famous binary trees can have at most two. Bounded by the laws isn't it?

binary search tree

It keeps the data in a sorted fashion allowing the search to be binary which improves the time complexity to O(log n). All nodes to the left of a root are smaller than it and to the right are greater. And this is valid for all sub-trees of the tree.

Representation can be done by having a node structure with a data field and a reference to the left and right nodes.

The search efficiency can be achieved, only if the tree is always balanced. Balanced here means that the root has almost equal number of elements at right and at it's left. This can be done by using AVL trees.

Found this meme on internet to make the idea more clear.