tree.txt

tree - used to store heirarchical data( a non linear data structure)
collection of entities called nodes linked together to form a heirarchy.
depth of node (x) - no of edges b/w root and x
height of node - number of edges in longest path from node to leaf node.
height of tree = height of root 

applications
storing natural heirarchical dat i.e , file system on computer
organise data for quick search insertion and deletion.ex - binary search tree
trie is used dictionaries
network routing algorithms


binary tree
-----------
each node can have atmost 2 children.
if tree has just one node then also its a binary tree

max number of nodes at any level i = 2^i

strict binary tree - if each node has either 0 or 2 children.

complete binary tree - if all levels except the last are completly filled and all nodes are as left as possible,

perfect binary tree - complete binary tree with all levels full.Number of nodes will be max, for height 'h'.
maximum number of nodes in a binary tree with height 'h' 
		- 2^0 +2^1+....+2^h
		= 2^(h+1) -1                                                            |################################|
			[ apply gp formula 1-r^(n+1)/(1-r)]                                   | log is base 2 unless specified |
	   	= 2^no of levels -1                                                   |################################|
	or if number of nodes is given 'n' then height = 
		n = 2^(h+1)-1
		h = log (n+1) -1
min height of complete binary tree = floor of log(n).
 maximum height of tree will be - n-1 (when we have a sparse tree where each node is placed one before other.)
height of tree with 0 node = -1
height of tree with just one node = 0

cost of various operations of tree depends upon the height of tree so we always try to keep the tree minimum or balanced.

Balanced binary tree
--------------------
difference between height of left and right subtree for every node is not more than k(mostly 1).
	diff = |height (left subtree) - height (right sub tree)|(absolute value)

we can implement tree using : 
-> dynamically created nodes.

-> Arrays(number nodes starting from root and number level by level left to right).they are mostly used to implement heaps.
--> in case of complete binary tree if we name the locations as this then to know :
the left childs index - 2i + 1
and right childs index - 2i + 2 (i - index of node)


Binary Search Tree 
------------------
a binary tree in which for each node value of all nodes in left subtree is smaller and in right subtree is greater.