Lowest Common Ancestor in Parent Array Representation | CPP program to find LCA in a tree represented as parent array . ; Maximum value in a node ; Function to find the Lowest common ancestor ; Create a visited vector and mark all nodes as not visited . ; Moving from n1 node till root and mark every accessed node as visited ; Move to the parent of node n1 ; For second node finding the first node common ; Insert function for Binary tree ; Driver Function ; Maximum capacity of binary tree ; Root marked
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1000 ; int findLCA ( int n1 , int n2 , int parent [ ] ) { vector < bool > visited ( MAX , false ) ; visited [ n1 ] = true ; while ( parent [ n1 ] != -1 ) { visited [ n1 ] = true ; n1 = parent [ n1 ] ; } visited [ n1 ] = true ; while ( ! visited [ n2 ] ) n2 = parent [ n2 ] ; return n2 ; } void insertAdj ( int parent [ ] , int i , int j ) { parent [ i ] = j ; } int main ( ) { int parent [ MAX ] ; parent [ 20 ] = -1 ; insertAdj ( parent , 8 , 20 ) ; insertAdj ( parent , 22 , 20 ) ; insertAdj ( parent , 4 , 8 ) ; insertAdj ( parent , 12 , 8 ) ; insertAdj ( parent , 10 , 12 ) ; insertAdj ( parent , 14 , 12 ) ; cout << findLCA ( 10 , 14 , parent ) ; return 0 ; }