Question

I'm playing around with writing a binary tree. Currently it's not going to be complete, or have each of it's levels full. I'm just trying to get the insert to work in it's most basic form (I'll mess around with re-ordering after that).

The Code

<?php

class Node {
    public $left = NULL;
    public $right = NULL;
    public $data = NULL;
}

class BinaryTree {
private $root = NULL;

public function insert($value, $node = false) {
    echo "VALUE: $value \n";
    if($node === false) {
        $node = $this->root;
    }

    if($node->data === NULL) {  // Always stuck here.
        $node->data = $value;
    } else {
        if($value <= $node->data) {
            $this->insert($value, $node->left);
        } else if($value >= $node->data) {
            $this->insert($value, $node->right);
        }
    }
}

}

$t = new BinaryTree();
$t->insert(7);
$t->insert(6);
$t->insert(1);

?>

The problem is that when I assign $node->value something, the $node object doesn't seem to be getting passed into the insert() function correctly. Because of this, it never gets passed the root.

Edit

@Joost pointed out I was missing a few steps. This led me to the following in my BinaryTree class:

public function __construct() {
    $this->root = new Node();
}
public function insert($value, $node = false) {
    if($node === false) {
        $node = $this->root;
    }

    if($node->data === NULL) {
        $node->data = $value;
    } else {
        if($value <= $node->data) {
            if(get_class($node->left) != "Node") {
                $node->left = new Node();
            }
            $this->insert($value, $node->left);
        } else if($value >= $node->data) {
            if(get_class($node->right) != "Node") {
                $node->rght = new Node();
            }
            $this->insert($value, $node->right);
        }
    }
}
Was it helpful?

Solution

It doesn't work because you never initialize the root. You can use a root that is always empty (init it in __construct) or directly assign a new node to the root on insert, if the root wasn't already set.

Actually, this problem is true for all nodes. You never create Node instances, neither do you set nodes as children of a parent.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top