LCA

lca.php

<?php
error_reporting(E_ALL ^ E_NOTICE);

function findLCA( $root, $a, $b)
{

    // no root no LCA.
    if (!$root) {
        return null;
    }

    // if either a or b is the root then root is LCA.
    if ($root->value == $a || $root->value == $b) {
        return $root->value;
    } else {
        // get LCA of a and b in left subtree.
        $l = findLCA($root->left, $a, $b);

        // get LCA of a and b in right subtree.
        $r = findLCA($root->right, $a, $b);

        // if one of a or b is in leftsubtree and other is in right
        // then $root it the LCA.
        if ($l && $r) {
            return $root->value;
        } // else if l is not null, l is LCA.
        else if ($l) {
            return $l;
        } else {
            return $r;
        }
    }

}

$tree = (object)[
    'value' => 5,
    'left' => (object)[
        'value' => 10,
        'left' => (object)[
            'value' => 7,
            'left' => (object)[
                'value' => 1,
            ],
            'right' => (object)[
                'value' => 45,
            ],
        ],
        'right' => (object)[
            'value' => 3,
        ],
    ],
    'right' => (object)[
        'value' => 30,
        'left' => (object)[
            'value' => 9,
        ],
        'right' => (object)[
            'value' => 13,
        ],
    ],
];

var_dump($tree);
var_dump(findLCA($tree, 1, 3));
var_dump(findLCA($tree, 1, 13));
var_dump(findLCA($tree, 7, 3));
var_dump(findLCA($tree, 7, 13));
var_dump(findLCA($tree, 7, 10));
var_dump(findLCA($tree, 45, 1));

/*
object(stdClass)#9 (3) {
["value"]=>
  int(5)
  ["left"]=>
  object(stdClass)#5 (3) {
  ["value"]=>
    int(10)
    ["left"]=>
    object(stdClass)#3 (3) {
    ["value"]=>
      int(7)
      ["left"]=>
      object(stdClass)#1 (1) {
      ["value"]=>
        int(1)
      }
      ["right"]=>
      object(stdClass)#2 (1) {
      ["value"]=>
        int(45)
      }
    }
    ["right"]=>
    object(stdClass)#4 (1) {
    ["value"]=>
      int(3)
    }
  }
  ["right"]=>
  object(stdClass)#8 (3) {
  ["value"]=>
    int(30)
    ["left"]=>
    object(stdClass)#6 (1) {
    ["value"]=>
      int(9)
    }
    ["right"]=>
    object(stdClass)#7 (1) {
    ["value"]=>
      int(13)
    }
  }
}
int(10)
int(5)
int(10)
int(5)
int(10)
int(7)
*/