Write an algorithm for Copying a Binary Tree in dfs (data file structure).

Question

What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?

Answer 1

PROCEDURE COPY(ROOT)
[Given a binary tree whose root node address is given by the pointer value ROOT and this algorithm generates a copy of the tree and returns the address of its root node. NEW is a temporary pointer variable].

1 [Cheching for empty tree]

If ROOT = NULL
then return (NULL).

2 [Creating a new node]

NEW <-- NODE.

3 [Copy information field]

DATA(NEW) <-- DATA(ROOT).

4 [Set the structural links]

LPTR(NEW) <-- COPY(LPTR(ROOT))
RPTR(NEW) <-- COPY(RPTR(ROOT))

5 [FINISH]
return(NEW).