261 What is a binary tree? Write an algorithm for the preorder traversal of a binary
tree using stacks.

Ans:
A binary tree 'T' is defined as
A finite set of elements, called nodes, such that: either (i) or (ii) happens:
(i) T is empty (called the 'null tree' or 'empty tree')
(ii) T contains a distinguished node R, called the 'root' of T and the
remaining nodes of 'T' form an ordered pair of the disjoint binary tree Tl
and T2.
If 'T' contains a root 'R' then the two trees Tl and T2 are called, the 'left' and
'right' sub trees of R, respectively.
Algorithm for the pre order traversal of a binary tree using a stack
A binary tree T is in memory, an array 'STACK' is used to temporarily hold the
addresses of the nodes. "PROCESS" is the operation that will be applied to each
node of the tree.
(1) Set TOP=1, STACK [1] =
NULL and PTR= ROOT
[initially push null onto
Stack and initialize PTR]
(2) repeat steps (3) to (5) while PTR != NULL
(3) apply PROCESS to INFO[PTR]
(4) [right child ?]
if RIGHT[PTR] != NULL then[push on STACK]
Set TOP=TOP+1 band STACK[TOP]=RIGHT[PTR]
[End of IF Structure]
(5) [Left Child ?]
if LEFT[PTR] != NULL then:
set PTR= LEFT[PTR]
else [POP from STACK]
set PTR=STACK[TOP] and TOP=TOP+1
[End of IF structure]
(6) Exit