LCA in binary tree

#1

can you send me code for this question.I’m getting error

#2

hey @dips123deepali_c25f140838182212 please refer to the below code for clarity .

#include <iostream>

#include <vector>

using namespace std;

// A Binary Tree node

struct Node

{

int key;

struct Node *left, *right;

};

// Utility function creates a new binary tree node with given key

Node * newNode( int k)

{

Node *temp = new Node;

temp->key = k;

temp->left = temp->right = NULL;

return temp;

}

// Finds the path from root node to given root of the tree, Stores the

// path in a vector path[], returns true if path exists otherwise false

bool findPath(Node *root, vector< int > &path, int k)

{

// base case

if (root == NULL) return false ;

// Store this node in path vector. The node will be removed if

// not in path from root to k

path.push_back(root->key);

// See if the k is same as root's key

if (root->key == k)

return true ;

// Check if k is found in left or right sub-tree

if ( (root->left && findPath(root->left, path, k)) ||

(root->right && findPath(root->right, path, k)) )

return true ;

// If not present in subtree rooted with root, remove root from

// path[] and return false

path.pop_back();

return false ;

}

// Returns LCA if node n1, n2 are present in the given binary tree,

// otherwise return -1

int findLCA(Node *root, int n1, int n2)

{

// to store paths to n1 and n2 from the root

vector< int > path1, path2;

// Find paths from root to n1 and root to n1. If either n1 or n2

// is not present, return -1

if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))

return -1;

/* Compare the paths to get the first different value */

int i;

for (i = 0; i < path1.size() && i < path2.size() ; i++)

if (path1[i] != path2[i])

break ;

return path1[i-1];

}

// Driver program to test above functions

int main()

{

// Let us create the Binary Tree shown in above diagram.

Node * root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

root->right->left = newNode(6);

root->right->right = newNode(7);

cout << "LCA(4, 5) = " << findLCA(root, 4, 5);

return 0;

}

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.