Lowest common ancestor in binary tree: perl, c and common lisp implementation

Find lowest common ancestor in binary tree. We assume the values in the tree are unique and the two values are always in the tree.

Time complexity O(n), Space complexity O(n)

C:

#include <stdio.h>
#include <stdlib.h>

// Find lowest common ancestor in binary tree. We assume the
// values in the tree are unique and the two values are always in
// the tree.

// Time complexity O(n)
// Space complexity O(n)

typedef struct Node
{
  int key;
  struct Node *left, *right;
} Node;

Node* createNode(int key)
{
  Node * tmp = (Node*)malloc(sizeof(Node));
  tmp->key = key;
  tmp->left = tmp->right = NULL;
  return tmp;
}

Node* findLCA(Node* root, int n1, int n2) {
  if (root == NULL) { return NULL; }
  if (n1 == root->key || n2 == root->key) { return root; }
  Node* left = findLCA(root->left, n1, n2);
  Node* right = findLCA(root->right, n1, n2);
  if (left && right) { return root; }
  return left ? left : right;
}

int main()
{
  Node* root = createNode(1);

  root->left = createNode(2);
  root->right = createNode(3);

  root->left->left = createNode(4);
  root->left->right = createNode(5);

  root->right->left = createNode(6);
  root->right->right = createNode(7);

  printf("LCA(4, 5) = %d\n", findLCA(root, 4, 5)->key);
  printf("LCA(4, 6) = %d\n", findLCA(root, 4, 6)->key);
  printf("LCA(3, 4) = %d\n", findLCA(root, 3, 4)->key);
  printf("LCA(2, 4) = %d\n", findLCA(root, 2, 4)->key);

  return 0;
}

Perl:

{% codeblock lang:perl %}

#!perl

use strict; use warnings; use utf8; use 5.014;

sub createNode { my $node = {}; $node->{VALUE} = $_[0]; $node->{LEFT} = $node->{RIGHT} = undef; $node; }

sub findLCA { # accept 3 arguments: # 1.node; 2. n1 value; 3. n2 value my($root, $n1, $n2) = @_; return undef unless ($root); return $root if ($n1 == $root->{VALUE} || $n2 == $root->{VALUE}); my($left, $right) = (findLCA($root->{LEFT}, $n1, $n2), findLCA($root->{RIGHT}, $n1, $n2)); return $root if ($left && $right); $left || $right; }

my ($root, $n); $root = createNode(1);

$root->{LEFT} = createNode(2); $root->{RIGHT} = createNode(3);

$root->{LEFT}{LEFT} = createNode(4); $root->{LEFT}{RIGHT} = createNode(5);

$root->{RIGHT}{LEFT} = createNode(6); $root->{RIGHT}{RIGHT} = createNode(7);

print “LCA(4, 5) = “, findLCA($root, 4, 5)->{VALUE}, “\n”; print “LCA(4, 6) = “, findLCA($root, 4, 6)->{VALUE}, “\n”; print “LCA(3, 4) = “, findLCA($root, 3, 4)->{VALUE}, “\n”; print “LCA(2, 4) = “, findLCA($root, 2, 4)->{VALUE}, “\n”;

{% endcodeblock %}

Common Lisp:

{% codeblock lang:lisp %} (defclass tree-node () ((value :initform nil :initarg :value :accessor value) (left :initform nil :accessor left-child) (right :initform nil :accessor right-child)))

(defun create-node (value) (let ((node (make-instance ‘tree-node :value value))) node))

(defun find-lowest-common-ancestor (tree-node n1 n2) (if (null tree-node) (return-from find-lowest-common-ancestor nil)) (if (or (equal n1 (value tree-node)) (equal n2 (value tree-node))) (return-from find-lowest-common-ancestor tree-node)) (let ((left (find-lowest-common-ancestor (left-child tree-node) n1 n2)) (right (find-lowest-common-ancestor (right-child tree-node) n1 n2))) (if (and left right) (return-from find-lowest-common-ancestor tree-node)) (or left right)))

(defparameter root (create-node 1))

(setf (left-child root) (create-node 2)) (setf (right-child root) (create-node 3))

(setf (left-child (left-child root)) (create-node 4)) (setf (right-child (left-child root)) (create-node 5))

(setf (left-child (right-child root)) (create-node 6)) (setf (right-child (right-child root)) (create-node 7))

(format t “LCA(4, 5) = ~d~%” (value (find-lowest-common-ancestor root 4 5))) (format t “LCA(4, 6) = ~d~%” (value (find-lowest-common-ancestor root 4 6))) (format t “LCA(3, 4) = ~d~%” (value (find-lowest-common-ancestor root 3 4))) (format t “LCA(2, 4) = ~d~%” (value (find-lowest-common-ancestor root 2 4))) {% endcodeblock %}