# Description

This is a function that uses left and right and returns a list containing a pre-order traversal of a binary tree BT.

A pre-order traversal prints the root, then the left child and then the right child.

# Code

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
list wasBinaryTreePreOrder(list BT, string node) {
string left = wasBinaryTreeLeft(BT, node);
string right = wasBinaryTreeRight(BT, node);
if(left == "" && right == "") return [ node];
if(left == "") return node + wasBinaryTreePreOrder(BT, right);
if(right == "") return node + wasBinaryTreePreOrder(BT, left);
return node + wasBinaryTreePreOrder(BT, left) + wasBinaryTreePreOrder(BT, right);
}

# Testing

Using the binary tree functions, we represent a flattened tree onto an array using the formulas described by the left and right functions.

Consider the above nodes to be a list, starting from index 0 and ended with index 6 which could represent a list with 7 elements. This could be, for example, the following list:

list BT = ["A", "B", "C", "D", "E", "F", "G"];

where element A is at index 0, element B is at index 1, and so on…

A pre-order traversal means that we print the the root, then the left-child and then the left child which means that the result we expect from an in-order traversal for this example is:

A B D E C F G

In order to test, we branch in the necessary functions and create a script:

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeLeft(list BT, string node) {
// Left child index: 2*i + 1
integer i = llListFindList(BT, (list)node);
if(i == -1) return "";
return llList2String(BT, 2*i+1);
}

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeRight(list BT, string node) {
// Right child index: 2*i + 2
integer i = llListFindList(BT, (list)node);
if(i == -1) return "";
return llList2String(BT, 2*i+2);
}

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeParent(list BT, string node) {
// Parent child: | \frac{i-1}{2} |
integer i = llListFindList(BT, (list)node);
if(i == -1) return "";
i = (i-1)/2;
if(i < 0) i *= -1;
return llList2String(BT, i);
}

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
list wasBinaryTreePreOrder(list BT, string node) {
string left = wasBinaryTreeLeft(BT, node);
string right = wasBinaryTreeRight(BT, node);
if(left == "" && right == "") return [ node];
if(left == "") return node + wasBinaryTreePreOrder(BT, right);
if(right == "") return node + wasBinaryTreePreOrder(BT, left);
return node + wasBinaryTreePreOrder(BT, left) + wasBinaryTreePreOrder(BT, right);
}

default {
state_entry() {
list BT = ["A", "B", "C", "D", "E", "F", "G"];
llOwnerSay(llDumpList2String(wasBinaryTreePreOrder(BT, "A"), ","));
}
}

And the output is:

[13:28]  Object: A,B,D,E,C,F,G