PHP Binary Tree Recursive Traversal Infinite Loop Issue

  binary-search-tree, class, php, recursion

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?

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());

Source: Ask PHP

LEAVE A COMMENT