B Figure 73 Valid Binary Trees Solutionnlr or preorder trave

Solution

nlr or preorder traversal can be done with trees or arrays

we can represent the binary tree using array as follows

if the root is ith element the

root:tree[root]

left child:tree[root+1]

right child:tree[root+2]

below is the array representation of the first tree in the question...

tree={\'A\',\'B\',\'D\',\'\\0\',\'E\',\'F\',\'\\0\',\'\\0\',\'\\0\',\'G\',\'H\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\'};
//Below is the java code for NLR scan you can convert it to c easyly if you want.

//save the below code as NLR.java and run it.

----------------------------------------------------------------------------------------------------

public class NLR {
public static void main(String args[])
{

//keep the tree here in the array format for which you wanted to perform nlr scan.
char[] tree={\'A\',\'B\',\'D\',\'\\0\',\'E\',\'F\',\'\\0\',\'\\0\',\'\\0\',\'G\',\'H\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\',\'\\0\'};
NLRScan(tree,0);
}

// Function that performs nlr scan.
static void NLRScan(char[] tree,int root)
{
System.out.print(tree[root]+\",\");
if(tree[(2*root)+1]!=\'\\0\')
NLRScan(tree,(2*root)+1);
if(tree[(2*root)+2]!=\'\\0\')
NLRScan(tree,(2*root)+2);
}
}

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

//example output for the above program which is using the first tree in the question.

A,B,E,G,H,D,F