Invert Binary Tree in PHP

Question

guys, I have this problem in PHP I'm trying to invert Binary Tree in PHP but I don't have an idea how to resolve this problem.

The task is to invert a binary tree, so the leaf's order is inverted.

Example:

inverts to:

Note: keep in mind that a tree can also be imbalanced.

/**
 * leaf data structure
 */
class BinaryNode {

    /** @var mixed null */
    public $value = null;
    /** @var BinaryNode null */
    public $left = null;
    /** @var BinaryNode null */
    public $right = null;

    /**
     * @param mixed $value
     */
    public function __construct( $value ) {
        $this->value = $value;
    }
}

class BinaryTree
{
    /**
     * @param BinaryNode $root
     * @return BinaryNode
     */
    public static function invert($root): BinaryNode
    {
        //$BinaryNode = new BinaryNode();

        if(!isset($root)) return $root;

        $tempLeftNode = $root->left;

        $root->left = $root->right;
        $root->right = $tempLeftNode;

        self::invert($root->left);
        self::invert($root->right);

        return  $root;

    }
}

$root = new BinaryNode(1);

$root->left = new BinaryNode(2);
$root->right = new BinaryNode(3);

$root->left->left = new BinaryNode(4);
$root->left->right = new BinaryNode(5);

$root->right->left = new BinaryNode(6);
$root->right->right = new BinaryNode(7);

print_r(BinaryTree::invert($root));

Your BinaryTree class has an invert method. Does it not work properly? What does it do? — Don't Panic
– Don't Panic, Commented Aug 22, 2018 at 19:49
Welcome to SO and good question. Just a note that your invert function returns null on leaves but this is disallowed by your return type, so consider fixing that to compile--if you remove the return type specifier, your code produces your desired output. — ggorlen
– ggorlen, Commented Aug 22, 2018 at 19:52
Welcome to SO and please test the answer. Interact with your question. :) — Rafael
– Rafael, Commented Aug 23, 2018 at 13:10
Thank you guys I removed the invert call and it works perfectly now — Osmair Coelho
– Osmair Coelho, Commented Aug 23, 2018 at 14:07

Rafael · Accepted Answer · 2018-08-23 14:16:08Z

2

You can do it using a recursively function... I remember doing an exercise like this years ago... Well, my solution would be something like this:

$array = [
    'a' => [
        'b1' => [
            'c1' => [
                'e1' => 4,
                'f1' => 5,
                'g1' => 6,
            ],
            'd1' => [
                'e11' => 4,
                'f11' => 5,
                'g11' => 6,
            ]
        ],
        'b2' => [
            'c2' => [
                'e2' => 4,
                'f2' => 5,
                'g2' => 6,
            ],
            'd2' => [
                'e21' => 4,
                'f21' => 5,
                'g21' => 6,
            ]
        ],
    ]
];

With the function:

function reverse_recursively($arrayInput) {
    foreach ($arrayInput as $key => $input) {
        if (is_array($input)) {
            $arrayInput[$key] = reverse_recursively($input);
        }
    }

    return array_reverse($arrayInput);
}

echo '<pre>';
print_r($array);
echo '<br>';
print_r(reverse_recursively($array));

And you can see the test here: https://3v4l.org/2pYhR

edited Aug 23, 2018 at 14:16

answered Aug 22, 2018 at 20:59

Rafael

1,5361 gold badge15 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Osmair Coelho Over a year ago

Thank you, Rafael, for sharing, I solved this problem, I appreciate your time

Rafael Over a year ago

If you did using this answer, upvote and mark the question as answered. :)

Nick · Accepted Answer · 2019-01-10 00:52:35Z

1

function invertTree($root) {

    if($root == null)
        return null;
    $flag = $root->right;
    $root->right = invertTree($root->left);
    $root->left = invertTree($flag);
    return $root;
}

edited Jan 10, 2019 at 0:52

Nick

147k23 gold badges67 silver badges106 bronze badges

answered Jan 10, 2019 at 0:22

Tarek Mahfouz

1461 silver badge3 bronze badges

Collectives™ on Stack Overflow

Invert Binary Tree in PHP

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related