The program
Long idea, short program

Input:
- Your program should take a binary tree in array form.
- The nodes of the tree are positive integers, a null value (leaf) may be represented as a -1.
- The tree is not a BST, it is simply a binary tree containing unique positive integers with no
particular ordering.
- The tree does not have to be full or complete.

- Your program should also take a sequence of three distinct integers as input

Action:

1) search/matching:
- Given the tree and the three integers (call them left, root, and right), your program should search the tree for the following formation:

That is: - The integer root at the root of the tree (or of some subtree) - The integer left somewhere in the left subtree of the root node - The integer right somewhere in the right subtree of the root node

- If this formation is not found in the binary tree, then return 0 and the algorithm ends.
- If this formation is found, then proceed to the next step:

2) color the paths

- We now have the indexes of left, root, and right in the array (the array represents the tree).
- Color the paths from left to root, and from right to root with the 'color' -2
- Include left, root, and right in the coloring
- The program finishes, the program doesn't return anything (other than the colored tree in memory).

Examples:

Consider the following tree and its associate array-implementation:

Tree:

Array:

The left, root, right sequence {4, 11, 5} is not in the tree, and if the program was given the above array and the latter sequence of integers, the returned value would be 0 (to indicate the formation was not found).

Likewise, the left, root, right sequence {3, 2, 4} is not in the tree and we would return 0.

The left, root, right sequence {6, 4, 25} is in this tree, and if the program was given the above array and the latter sequence of integers, the result would be:

The left, root, right sequence {100, 1, 18} is also in this tree, and if the program was given the above array and the latter sequence of integers, the result would be:

The algorithm/pseudocode:

Working with a binary in array-form:
- index of node: i
- index of node's left-child: 2i
- index of node's right-child: 2i + 1
- index of node's parent: floor(i/2)

Depth-First Search:
- Recursive
- Takes a starting node index and a value to search for (we assume the array is global)
- Returns the index of the value if it is present in the tree, o/w returns 0.

int DFS(index, value){

int temp;

// Return this index if we've found the value
if(tree[index] == value)
return index;

// Return 0 if we are at a leaf (since we didn't find value)
if(tree[index] == -1)
return 0;

// If we're not at a leaf and we haven't found value, then
// search the left subtree
temp = DFS(2*index, value);

// If we found value, then return its index
if(temp != 0)
return temp;

// O/w, continue the search in the right subtree
return DFS(2* index + 1, value);
}


Searching for the left, root, right formation:
- One strategy

int findFormation(int left, int root, int right){

int i, j, k;

// Try to find 'root'
i = DFS(1, root);
if(i == 0)
return 0;

// Then we found 'root', so try to find 'left' in 'root's
// left subtree.
j = DFS(2*i,left);
if(i == 0)
return 0;

// Then we found 'left' in 'root's left subtree, so search for
// 'right' in 'root's right subtree.
k = DFS(2*i + 1, right);
if(i == 0)
return 0;

// Then we've found 'left', 'root', and 'right' in the correct
// formation. Now we color the paths between 'left' and 'root', and
// between 'right' and 'root', and we're done.
color(j, i);
color(k, i);
}


void color(int end, int root){

int temp;

temp = end;
while(temp != root){
// Color this node
tree[temp] = -2;

// Step up to this node's parent
temp = floor(temp / 2);
}
}


hints:
- X >> 1 is the same as floor(X/2)
- 2 * i is the same as i + i

If you find any problems implementing this program, please email me.