PHP Code to create a BST and print it in Breadth First Order

/* take an array
 class node. take an element. traverse until the bst condition satisfies.

*/


class node
{
  public $value;
  public $left;
  public $right;
}

$input = array(5,7,3,4,2,6,9);

//  create a parent.

/*
  5
      3                  7
 2       4       6            9      

*/

$current = 0;

$parent = new node();
$parent->value = $input[$current++];
$parent->left = null;
$parent->right = null;

// take next element. see the bst condition.

$currentNode = $parent;

while( $current < count($input) )
{
// take the comparison here.
// move to the left or right accordingly.
// is it ready to insert  ?
if( $input[$current] >= $currentNode->value )
{
// currentNode needs to move to right.
// check if right is null.
if( $currentNode->right == null )
{
$currentNode->right
                        = createNewNode(& $input, & $current);
}
else
{
// advance current to its right.
$currentNode = $currentNode->right;
}
}
else if ( $input[$current] < $currentNode->value )
{

if( $currentNode->left == null )
{
$currentNode->left
                        = createNewNode(& $input, & $current);
}
else
{
// advance current to its left
$currentNode = $currentNode->left;
}
}
}

// Traverse the tree in BFT
// take the top, push all children. print current node.
// go to next level if all done with current level
// same logic almost.

$BFTQueue = array();

array_unshift($BFTQueue,  $parent);

echo "visit: ".$parent->value;

while( count($BFTQueue) > 0 )
{
// next level.
$BFTCurrent = array_pop($BFTQueue);

// print the value and push
echo "visit: ".$BFTCurrent->value;

if($BFTCurrent->left)
{
        array_unshift($BFTQueue, $BFTCurrent->left);
}
if($BFTCurrent->right)
{
        array_unshift($BFTQueue, $BFTCurrent->right);
}

}


function createNewNode($input, $current)
{
$newNode = new node();
$newNode->value = $input[$current++];
$newNode->left=null;
$newNode->right=null;

return $newNode;
}

PHP Code to Create Binary Tree and Breadth First Traversal

/*
        create a binary tree with some input given.

see what level I'm in.
level x, see if I have so many elements in the input
pop 2^(x-1) elements from queue. keep adding left and rights to those.

        1
    2       3
  4  5    6   7
 8 9

*/


class node
{
        public $left;
        public $right;
        public $value;
}

$input = array(1,2,3,4,5,6,7,8,9);

$queue = array();

$i = 0;

$level = 2;
$max = count($input);

$current = new node();
$current->value = $input[$i++];
$current->left = null;
$current->right = null;

array_unshift($queue,  $current);

echo $current->value." ";

while ( $i < $max )
{
        $j = pow(2,$level-1);

        // create nodes until 2^(level-1) and
        while( $j > 0  && $i < $max )
        {

                $parent = array_pop($queue);

                // create a left node
                $newLeft = new node();
                $newLeft->value = $input[$i++];
                $newLeft->left = null;
                $newLeft->right = null;

                $parent->left =  $newLeft;
                array_unshift($queue, $newLeft);

                $j--;

                if($i >= $max || $j <= 0)
                {
                   break;
                }

                // create right node
                $newRight = new node();
                $newRight->value = $input[$i++];
                $newRight->left = null;
                $newRight->right = null;

                $parent->right = $newRight;
                array_unshift($queue, $newRight);

                $j--;
                echo print_r($parent,1);

        }

        $level++;
        echo "level :".$level;
        //echo print_r($queue,1);
}

// Traverse the tree in BFT
// take the top, push all children. print current node.
// go to next level if all done with current level
// same logic almost.

$BFTQueue = array();

array_unshift($BFTQueue,  $current);

echo "visit: ".$current->value;

while( count($BFTQueue) > 0 )
{
// next level.
$BFTCurrent = array_pop($BFTQueue);

// print the value and push
echo "visit: ".$BFTCurrent->value;

if($BFTCurrent->left)
{
        array_unshift($BFTQueue, $BFTCurrent->left);
}
if($BFTCurrent->right)
{
        array_unshift($BFTQueue, $BFTCurrent->right);
}

}

PHP Code for Unique Pairs of Elements in an array

Find all unique pairs of element in an array that sum to S. For ex. If array = {2,4,6,4,6} and S = 8 then answer is {(2,6), (4,4)}


// take the array.
$elements = array(1,2,3,4,6,4, 1);
$sum = 2;
sort($elements);

// now that it took nlogn, we should do away with O(n) next.
$left = 0;
$right = count($elements)- 1;

echo "left value=".$left." right value=".$right;

// goto the sum value. one value lesser than sum actually
for ( $i = $right; $elements[$i] > $sum; $i--)
{}


// final logic. now loop thru
// left should never be greater than right.
// if sum-right is greater than left -> increment left
// if sum-right is less than left -> stop there. this element has no pair. and decrement right.
for( ; $left < $right; )
{
        if( ($sum - $elements[$right]) > $elements[$left])
        {
                // increment left
                $left++;
        }
        else if( ($sum - $elements[$right]) < $elements[$left] )
        {
                // decrement right. no pair found
                $right--;
        }
        else
        {
                // equals output a pair. and decrement right.
                echo "Pair: (".$elements[$left].",".$elements[$right].")";
                // now decrement right until duplicates are all skipped.
                for( $dec = $elements[$right];
                       $dec == $elements[$right];
                       $right--){}
        }
}

The solution is O(n logn) .. can we do better ?