Concepts Used

DFS , Recursion

Difficulty Level

Medium

Problem Statement :

"Lowest common ancestor of two node n1 and n2 is the lowest node in the tree that has both n1 and n2 as descendents(where we allow a node to be a descendant of itself)."

Given a binary tree and two values, our task is to return the node which is lowest common ancestor of the two values.

See original problem statement here

Solution Approach :

Introduction :

Lowest Common Ancestor (LCA) of two nodes n1 and n2 in the tree is the shared ancestor of n1 and n2 that is located farthest from the root.

Method 1:

We can begin by storing path of each node starting from the root one-by-one.

By the definition of LCA above, we know that there must be some nodes (atleast one), which are common in both the paths we have stored. (Unless the root itself is LCA ).

Suppose we need to find LCA of the nodes n1 & n2. So,we will search for the nodes n1 & n2 in the given tree and store their paths starting from the root node. Now we will start traversing both the path arrays till the values stored in the arrays matches.

As soon as the values become different we will stop & return the last value which matches both the path arrays. This value is our required LCA.

Method 2 (Efficient):

We can reduce the traversal to just once, without using any extra space using following points referred from the best sites to learn coding:

  • If root matches any of the values n1 or n2, then root is the LCA.
  • Else, we will recurvisely call the function for its left & right subtrees. The node which has one value present in its left subtree and the other value present in right subtree is the LCA.
  • If both values lies in the left subtree, then LCA lies in the left subtree, otherwise LCA lies in right subtree.

Complexity Analysis :

In the first method, although it is O(n) in case of time complexity but we are traversing the arrays 3 times (twice for storing the path and once for finding the LCA), with an extra space for path arrays but in the second method we are traversing the array just once also the space complexity is O(1) of second method.

SOLUTIONS:

#include <stdio.h>

#include<stdlib.h>

#define ll long long

#define REP(i, n) for (i = 0; i < n; i++)



struct nodelist

{

    ll value;

    struct nodelist *left;

    struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

    int front, rear, size;

    unsigned capacity;

    node* *array;

};

typedef struct Queue queue;



queue* createQueue(unsigned capacity)

{

    queue* qu =(queue*)malloc(sizeof(queue));

    qu->capacity = capacity;

    qu->front = qu->size =0;

    qu->rear = capacity-1;

    qu->array = (node **)malloc(qu->capacity * sizeof(node));

    return qu;

}



int isFull(queue*  queue1)

{

    return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

    return (queue1->size==0);

}



void enqueue(queue* queue1, node* item)

{

    if(isFull(queue1))

        return ;

    queue1->rear = (queue1->rear +1 )%queue1->capacity;

    queue1->array[queue1->rear] = item;

    queue1->size = queue1->size +1;



}



node dequeue(queue* queue1)

{

    node* item = queue1->array[queue1->front];

    queue1->front = (queue1->front +1)%queue1->capacity;

    queue1->size = queue1->size -1;

    return *item;

}



node* front(queue* queue1)

{

    return queue1->array[queue1->front];

}



node* rear(queue * queue1)

{

    return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

    node *t= (node *) malloc(sizeof(node));

    t->value = value;

    t->right = t->left = NULL;

    return  t;

}

void deleteNode(node*t)

{

    free(t);

}



node *replaceNegativeOne(node *root)

{

    if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



void deleteTree(node *node1)

{

    if(node1==NULL)

        return;

    deleteTree(node1->left);

    deleteTree(node1->right);

    free(node1);

}

node *createTreeByLevelTree()

{

    ll n,m;

    queue* queue1 = createQueue(100000);

    node *root, *t;

    root = NULL;

    while(scanf("%lld", &n))

    {

        if(isEmpty(queue1))

        {

            root= createNode(n);

            enqueue(queue1,root);

            continue;

        }

        scanf("%lld", &m);

        t = front(queue1);

        dequeue(queue1);

        t->left =createNode(n);

        t->right=createNode(m);

        if(t->left->value !=-1)

            enqueue(queue1,t->left);

        if(t->right->value !=-1)

            enqueue(queue1,t->right);



        if(isEmpty(queue1))

            break;

    }

    return root;

}

node* findLowestAncestor(node* root, int v1, int v2)

{

    if(root== NULL)

     return root;



    if(root->value == v1 || root->value == v2 )

     return root;



    node * left = findLowestAncestor(root->left,v1,v2);

    node* right = findLowestAncestor(root->right,v1,v2);



    if(left && right)

     return root;



    return (left)?left:right;



}
int main() {



    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    int n1,n2;

    scanf("%d %d",&n1,&n2);

    node *val = findLowestAncestor(root, n1,n2);

    printf("%lld\n", val->value);

    deleteTree(root);

    return 0;



}
#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

    ll value;

    node *left;

    node *right;

};



node *createNode(ll value)

{

    node *t = new node();

    t->value = value;

    t->right = t->left = NULL;

    return t;

}



void deleteNode(node *t)

{

    delete t;

}





node *replaceNegativeOne(node *root)

{

    if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



node *createTreeByLevelTree()

{

    ll n, m;

    queue<node *> q;



    node *root, *t;



    root = NULL;



    while (cin >> n)

    {

        if (q.empty())

        {

            root = createNode(n);

            q.push(root);

            continue;

        }

        cin >> m;



        t = q.front();

        q.pop();



        t->left = createNode(n);

        t->right = createNode(m);



        if (t->left->value != -1)

        {

            q.push(t->left);

        }



        if (t->right->value != -1)

        {

            q.push(t->right);

        }

         if (q.empty())

        {

            break;

        }

    }



    return root;

}



void deleteTree(node *node)

{

    if (node == NULL)

        return;



    deleteTree(node->left);

    deleteTree(node->right);

    delete node;

}

node* findLowestAncestor(node* root,int v1, int v2)

{

    if(root==NULL)

     return root;



    if(root->value == v1 || root->value == v2)

     return root;



    node* left = findLowestAncestor(root->left,v1,v2);

    node* right = findLowestAncestor(root->right,v1,v2);



    if(left && right)

     return root;



    return (left)?left:right;

}
int main()

{

    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    int n1, n2;

    cin>>n1>>n2;

    node* val =findLowestAncestor(root,n1,n2);

    cout<<val->value<<endl;

    deleteTree(root);

    return 0;

}

import java.util.LinkedList;

import java.util.*;

import java.util.Scanner;

import java.io.*;



class Node

{

    long value;

    Node left, right;



    public Node(long item)

    {

        value = item;

        left = right = null;

    }

}

class BinaryTree {

    Node root;



    BinaryTree() {

        root = null;

    }



    Node createNode(long value) {

        Node t = new Node(value);

        return t;

    }



    Node replaceNegativeOne(Node root) {

        if (root == null || (root.value == -1 && root.left == null && root.right == null)) {

            return null;

        }

        root.left = replaceNegativeOne(root.left);

        root.right = replaceNegativeOne(root.right);

        return root;

    }



    Node createTreeByLevelTree(Scanner sc ) {



        long n, m;

        LinkedList<Node> queue = new LinkedList<>();

        Node t;

        root = null;

        while (sc.hasNext()) {

            n = sc.nextLong();

            if (queue.isEmpty()) {

                root = createNode(n);

                queue.add(root);

                continue;

            }

            m = sc.nextLong();

            t = queue.peekFirst();

            queue.pop();

            t.left = createNode(n);

            t.right = createNode(m);

            if (t.left.value != -1)

                queue.add(t.left);

            if (t.right.value != -1)

                queue.add(t.right);

            if (queue.isEmpty())

                break;

        }

          return root;

    }

    void deleteTree(Node node) {

        node = null;

    }


Node findLowestAncestor(Node node, int v1, int v2) {

    if(node == null)

     return node;



    if(node.value == v1 || node.value == v2)

     return node;



    Node left = findLowestAncestor(node.left,v1,v2);

    Node right = findLowestAncestor(node.right,v1,v2);



    if(left!=null && right!= null)

     return node;



    return (left!=null)?left:right;

}




}

public class Main {



    public static void main(String[] args) {

        // write your code here

        Scanner sc = new Scanner(System.in);

        BinaryTree bt = new BinaryTree();

        bt.root = bt.createTreeByLevelTree(sc);

        bt.root = bt.replaceNegativeOne(bt.root);

        int n1 = sc.nextInt();

        int n2 = sc.nextInt();

        Node val = bt.findLowestAncestor(bt.root, n1,n2);

        System.out.println(val.value);

        bt.deleteTree(bt.root);

    }

}

    }

Previous post Inorder Traversal
Next post LevelOrder Traversal

Leave a Reply

Your email address will not be published. Required fields are marked *