Binary tree
A binary tree T is defined as a finite set of elements, called nodes such that
a) T is empty (called the null or empty tree) or
b) T contains a distinguished node R, called root of T and remaining nodes of T form an
ordered pair of disjoint binary trees T1 and T2.
B
C
D E G H
F J K
If T contains root R then two trees T1 and T2 are left and right subtrees of R. if T1 is nonempty
then its root is called left successor of R and if T2 is nonempty then its root is called right
successor of R.
Suppose N is node in T with left successor S1 and right successor S2. Then N is called parent of
S1 and S2. S1 is left child of N and S2 is right child of N. The line drawn from node to successor
is called edge and sequence of consecutive edges is called a path. A terminal node is a leaf and
path ending in a leaf is called branch. The depth of tree T is the maximum number of nodes in
a branch of T. In above example the depth of tree is 5. The maximum number 0f nodes of
symmetric binary tree with depth n is 2n-1. If depth of symmetric binary tree is 5 them
maximum number of nodes are 31.
Representation of binary tree in memory
1. Linked representation
The linked representation of binary tree uses three parallel arrays INFO, LEFT, RIGHT and a
pointer variable ROOT. Each node N of T will correspond to a location K such that
1. INFO[K] contains data at node N
2. LEFT[K] contains the location of left child
3. RIGHT[K] contains the location of right child
ROOT will contain location of root R of T
4 A 5
X B X X C X
INFO LEFT RIGHT
1
2 2 A 4 5
3
4 B 0 0
5 C 0 0
2. Sequential Representation
In sequential representation linear array is used. The root R is stored in TREE[1]. If node N
occupies TREE[K], its left child is stored in TREE[2*K] and right child in TREE[2*K+1].
B C
D E
TREE
A
B
C
0
0
D
E
Stack and Queue
When we want to restrict insertion and deletion operations so they can take place only at
beginning or the end of list and not in the middle. In this situation data structures Stack and
Queue are useful.
A stack is data structure in which items may be added or removed only at one end. The
examples of stack are the stack of dishes or stack of books etc. the item can be removed or
added at only from the top of the stack. ‘PUSH’ is the term used to insert an element into
stack and ‘POP’ is the term used to remove or delete an element from the stack. A stack is also
called as Last-In-First-Out (LIFO) list.
Queue is data structure in which items may be added only at one end and items may be
removed only at other end. Example of queue is the queue waiting for a bus at bus stop. A
Queue is also called as First-In-First-Out (FIFO) list.