binary_tree.php

<?php
    class Node
    {
        public $data;

        public $left;

        public $right;

        public $nextRight;
        
    }

    function newNode($data)
    {
        $p=new Node;
        $p->data=$data;
        $p->left=null;
        $p->right=null;
        $p->nextRight=null;
        return $p;
    }

    function connect( &$p )
    {
        $p->nextRight=null;

        recursion ( $p );
    }

    function recursion ( &$p )
    {
        // Base case
        if (!$p)
            return;

        // Set the nextRight pointer for p's left child
        if ($p->left)
            $p->left->nextRight = $p->right;

        // Set the nextRight pointer for p's right child
        // p->nextRight will be NULL if p is the right most child at its level
        if ($p->right)
            $p->right->nextRight = ($p->nextRight)? $p->nextRight->left: NULL;
        
        
        // Set nextRight for other nodes in pre order fashion
        recursion ($p->left);
        recursion ($p->right);    
    }

    function output($p)
    {
        echo $p->data."<br/>";
        
        print_output ($p);
    }
    
    function print_output($p)
    {
        if (!$p)
            return;
        
        if ($p->left) echo $p->left->data."  -  ";
        if ($p->right) echo $p->right->data."   ";
        
        print_output($p->left);
        print_output($p->right);
    }
    
    $root= new Node;
    $root->data=1;
    $root->left=newNode(2);
    $root->right=newNode(3);
    $root->left->left=newNode(4);
    $root->left->right=newNode(5);
    $root->right->left=newNode(6);
    $root->right->right=newNode(7);
    connect($root);
    output($root);
    d($root);