Binary Tree

Binary Trees
A binary tree is a tree in which each node can have maximum two children.
Thus each node can have no child, one child or two children

Consider a set of numbers: 25,63,13, 72,18,32,59,67.
we store these numbers in individual nodes of a singly linked list
To search for a particular item we have to go through the list, and maybe we have to go to the end of the list as well.
Thus if there were n numbers, our search complexity would be O(n).

suppose we order these numbers:
13,18,25,32,59,63,67,72. and store these in another linked list.
search complexity is still O(n)

You simply cannot apply binary search on a linked list with O(log n) complexity.
So a linear linked structure is not helping

The value at any node is more than the values stored in the left-child nodes,
and less than the values stored in the right-child nodes

Implementation
• A binary tree has a natural implementation in linked storage.
A tree is referenced with a pointer to its root.

A tree is a node with structure that contains more trees.
We have actually a tree  located at each node of a tree.

http://www.cs.ucf.edu/courses/cop3502h.02/trees1.pdf