PHP Binary Tree Recursive Traversal Infinite Loop Issue-CodePudding

I have a binary tree and node class that can create nodes and then recursively traverse the root for pre, post and in-order node orders. This code works when in JS, but for some reason infinitely loops with a warning of "Cannot use '$this' in non-object context." when returning $this in the addSide() function. What is causing this infinite loop, and how can I fix it?

<?php

class Node {
      public $value;
      public $right = null;
      public $left = null;

      function __constructor($value) {
        $this->value = $value;
      }
    }

    class BinaryTree {
      public $root;

      function __constructor() {}

      function create($value) {
        $newNode = new Node($value);
        if (!$this->root) {
          $this->root = $newNode;
          return $this; //no warning
        }
        $current = $this->root;

        function addSide($side, $current, $newNode) {
          if (!$current->$side) {
            $current->$side = $newNode;
            return $this; //Warning: "Cannot use '$this' in non-object context."
          }
          $current = $current->$side;
        };
        while (true) {
          if ($value === $current->value) return $this;
          if ($value < $current->value) addSide("left", $current, $newNode);
          else addSide("right", $current, $newNode);
        }
      }

      function preOrder() {
        $visited = [];
        $current = $this->root;

        function traversePreOrder($node) {
          array_push($visited, $node->value);
          if ($node->left) traversePreOrder($node->left);
          if ($node->right) traversePreOrder($node->right);
        };
        traversePreOrder($current);
        return $visited;
      }

      function postOrder() {
        $visited = [];
        $current = $this->root;

        function traversePostOrder($node) {
          if ($node->left) traversePostOrder($node->left);
          if ($node->right) traversePostOrder($node->right);
          array_push($visited, $node->value);
        };

        traversePostOrder($current);
        return $visited;
      }

      function inOrder() {
        $visited = [];
        $current = $this->root;

        function traverseInOrder($node) {
          if ($node->left) traverseInOrder($node->left);
          array_push($visited, $node->value);
          if ($node->right) traverseInOrder($node->right);
        };

        traverseInOrder($current);
        return $visited;
      }
    }

    $tree = new BinaryTree();

    $tree->create(50);
    $tree->create(30);
    $tree->create(45);
    $tree->create(12);
    $tree->create(29);

    echo("inOrder: ". $tree->inOrder());
    echo("preOrder: ". $tree->preOrder());
    echo("postOrder: ". $tree->postOrder());

CodePudding user response：

Since you don't seem to be from a PHP background, here are some of the things to note down:

It is __construct() and not __constructor(). This served to be a major problem in the code during value comparisons.
No need to create functions inside functions. This can lead to cannot redeclare function issues when a method is called twice.
When calling a method from another method inside a class, $this-> is necessary unless the function being called is an inbuilt function in PHP or at least available during code execution.
You seem to be creating a Binary Search Tree instead of just a Binary Tree.
Pass $visited by reference when collecting values during traversal.
You can't print arrays using echo. Use print_r() or use implode() to convert the array to string using a delimiter(say ,) and then print it using echo.
In create(), you sometimes return a node and sometimes $this. Both are not the same. Former one is an object of the Node class and the latter one is the object of the BinaryTree class.
In create() method, you simply need to traverse left or right from the current code according to the given value, which can be achieved using a simple while loop.

Corrected Code:

<?php

class Node {
  public $value;
  public $right = null;
  public $left = null;

  function __construct($value) {
    $this->value = $value;
  }
}

class BinaryTree {
  public $root;

  function __construct() {
    $this->root = null;
  }

  function create($value) {
    $newNode = new Node($value);
    if ($this->root === null) {
      $this->root = $newNode;
      return $newNode; //no warning
    }

    $current = $this->root;
    while($current !== null){        
        if($current->value > $value){
            if($current->left === null){
                $current->left = $newNode;
                break;
            }else{
                $current = $current->left;
            }
        }else if($current->value < $value){
            if($current->right === null){
                $current->right = $newNode;
                break;
            }else{
                $current = $current->right;
            }
        }else{
            throw new \Exception("Node with $value already exists.");
        }
    }
    
    return $newNode;
  }

  function preOrder() {
    $visited = [];
    $current = $this->root;
     $this->traversePreOrder($current,$visited);
    return $visited;
  }

  function traversePreOrder($node,&$visited) {
    array_push($visited, $node->value);
    if ($node->left !== null)  $this->traversePreOrder($node->left,$visited);
    if ($node->right !== null)  $this->traversePreOrder($node->right,$visited);
  }

  function postOrder() {
    $visited = [];
    $current = $this->root;
    $this->traversePostOrder($current,$visited);
    return $visited;
  }

  function traversePostOrder($node,&$visited) {
    if ($node->left !== null)  $this->traversePostOrder($node->left,$visited);
    if ($node->right !== null)  $this->traversePostOrder($node->right,$visited);
    array_push($visited, $node->value);
  }

  function inOrder() {
    $visited = [];
    $current = $this->root;
    $this->traverseInOrder($current,$visited);
    return $visited;
  }

  function traverseInOrder($node,&$visited) {
    if ($node->left != null)  $this->traverseInOrder($node->left,$visited);
    array_push($visited, $node->value);
    if ($node->right !== null)  $this->traverseInOrder($node->right,$visited);
  }
}

$tree = new BinaryTree();

$tree->create(50);
$tree->create(30);
$tree->create(45);
$tree->create(12);
$tree->create(29);

echo "inOrder: ". implode(",",$tree->inOrder()),PHP_EOL;
echo "preOrder: ". implode(",",$tree->preOrder()),PHP_EOL;
echo "postOrder: ". implode(",",$tree->postOrder()),PHP_EOL;

Online Demo