Trees
TREE
Tree is defined as T (V,E) where V = set of vertices and E = set of edges.In a tree there is exactly one edge between a pair of vertices and there are no cycles and self loops.
The degree of a node in the tree is defined as the maximum number of children that node can hold.A tree can never be empty, but binary tree may be empty.
Internal node ( I ): A node having minimum of 1 child is know as internal node.
Leaf node ( L ): A node having no children.
External node ( E ): The replacement of null leaves are external nodes.
Properties:-
(i) For 'n' nodes there are (n-1) edges.
(ii) Let,
Tree is defined as T (V,E) where V = set of vertices and E = set of edges.In a tree there is exactly one edge between a pair of vertices and there are no cycles and self loops.
The degree of a node in the tree is defined as the maximum number of children that node can hold.A tree can never be empty, but binary tree may be empty.
Internal node ( I ): A node having minimum of 1 child is know as internal node.
Leaf node ( L ): A node having no children.
External node ( E ): The replacement of null leaves are external nodes.
Properties:-
(i) For 'n' nodes there are (n-1) edges.
(ii) Let,
n0 = number of nodes with degree 0.
n2 = number of nodes with degree 2.
n0 = n2
+ 1
(iii) ( In heap array ) If child is at location i (index starts from 0 ) then parent is at location [ (i-1)/2].
If parent is at location i ( index starts at 0 ) then left child is at location 2i + 1 and Right child is at location 2i + 2.
(iv) (In heap array) If parent is at location i (indexing at 1 ) then Left child is at location 2i and Right child is at location 2i + 1.
If child is at location i (indexing at 1 ) then parent is at location [i/2].
(v) In a linked representation of binary tree,if there are 'n' nodes then number of NULL links = n + 1.
Complete Binary Tree is a tree in which nodes are inserted/filled from left to right. All the leaves may not be at the same level.
Full Binary Tree is a tree in which every node has exactly 2 children and all the leaves are at the same level.
All full binary trees are complete binary trees but vice versa is not true.
Strict Binary Tree is a tree in which each node has exactly 0 or 2 children.
A complete n-any tree is one in which every node has '0' or 'n' sons. If 'x' is the number of internal nodes of a complete n-any tree, the number of leaves in it is: x(n-1) + 1.
Let T(n) be the number of different binary search trees on n-distinct element , then
T(n) = ∑ T(k-1) T(n-k+1).
In binary tree, Rank (or) Index of any node.
Rank(i) = (Number of nodes in left subtree of i) + 1
In a m-ary tree (degree = m), if ni is number of nodes of degree 'i'.
( i = 0,1,.....,m) then n0 (leaf nodes) = 1 + ⅀ (i - 1)ni.
Maximum size of array to store a binary tree with 'n' nodes = 2n - 1.
Minimum size of array to store a binary tree with 'n' = 2[log(n-1)] - 1.
Maximum height possible for a binary tree with 'n' nodes = n.
Minimum height possible for a binary tree with 'n' nodes = Log2 n.
Maximum number of nodes in a binary tree of height 'h' = 2h+1 – 1.
Total number of binary trees possible with n nodes = 2nCn / (n+1)
For non-empty binary tree , if n is number of nodes and e is the number of edge , then n = e + 1.
Binary Tree Traversals
Traversing a tree means a visiting each node in a specified order.
Traversal Techniques
1. Preorder ( Root , Left, Right).
2.Inorder (Left, Root,Right)
3.Postorder(Left,Right,Root)
No comments