# Tree Practice Problems in C++

## Lowest Common Ancestor of Two Nodes of a Binary Search Tree in C++

• In this question we want to find the parent of two given nodes which will be the lowest common ancestor

• We can perform a recusive function that moves to the right and left subtrees when needed!

Code

``````#include<iostream>
using std::cout;
using std::endl;

struct Node {

int data;
struct Node *left;
struct Node *right;
};

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,int data) {
// Return pointer which is a memory address

if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
}

else if(data <= root->data)
{
root->left = Insert(root->left,data);
}
else
{
root->right = Insert(root->right,data);
}
return root;  // Return Root Address
}

Node* lca(Node* root, int n1, int n2)
{
// Return the Node* to the  Lowest Common Ancestor of n1 and n2

if (root == NULL)
{ // BST doesn't exist
return NULL;
}

// If both n1 and n2 are smmaller than the root, the lowest common ancestor lies to the left, so recusive call to the left-subtree
if (root->data > n1 && root->data > n2)
{
return lca(root->left, n1, n2);
}

// If both n1 and n2 are greater than the root, then LCA lies in the right, so recusive call to the right-subtree
if (root->data < n1 && root->data < n2)
{
return lca(root->right, n1, n2);
}

return root; // Return root of LCA
}

int main() {

Node* root = NULL;

root = Insert(root,20);
root = Insert(root,12);
root = Insert(root,55);
root = Insert(root,8);
root = Insert(root,15);
root = Insert(root,36);
root = Insert(root,75);
root = Insert(root,69);
root = Insert(root,90);

int n1 = 8, n2 = 15;
Node *t = lca(root, n1, n2);
cout << endl;
cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl;

int n3 = 36, n4 = 75;
Node *t2 = lca(root, n3, n4);
cout << endl;
cout << "LCA of " << n3 << " and " << n4 << " is " << t2->data << endl;

int n5 = 69, n6 = 90;
Node *t3 = lca(root, n5, n6);
cout << endl;
cout << "LCA of " << n5 << " and " << n6 << " is " << t3->data << endl;
cout << endl;
}
``````

Output:

``````LCA of 8 and 15 is 12

LCA of 36 and 75 is 55

LCA of 69 and 90 is 75
``````

## Invert a Binary Tree in C++

• The Algorithm to Invert is a simple recursuve algorithm!
1. Invert Right-Subtree - Recursively
2. Invert Left-Subtree - Recursively
3. Swap Left and Right Subtrees - Use temp node

Code

``````#include<iostream>
using std::cout;
using std::endl;

#include <queue>
using std::queue;

struct Node {
int data;
struct Node *left;
struct Node *right;
};

Node* Insert(Node *root,int data) {

if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
}

else if(data <= root->data)
{
root->left = Insert(root->left,data);
}
else
{
root->right = Insert(root->right,data);
}
return root;
}

void printLevelOrder(Node *root)
{
if (root == NULL)
{	return;  }

queue<Node*> q;

int count_depth = -1;
q.push(root);

while (q.empty() == false)
{
int NodeCount = q.size();

while (NodeCount > 0){

Node *Node = q.front();

cout << Node->data << " ";
q.pop();
if (Node->left != NULL)
{
q.push(Node->left);
}
if (Node->right != NULL)
{
q.push(Node->right);
}
NodeCount--;
}
count_depth++;
cout << endl;
}
}

void invert(Node* node){

// Invert/Mirror Binary Tree.. Recursive Approach
if (node == NULL){
return;
}
else{

invert(node->left);
invert(node->right);

Node* temp;

temp = node->left;
node->left = node->right;
node->right = temp;
}
}

int main() {

Node* root = NULL;

root = Insert(root,20);
root = Insert(root,12);
root = Insert(root,40);
root = Insert(root,35);
root = Insert(root,52);
root = Insert(root,48);
root = Insert(root,60);

cout << "Print Level Order for Tree 1 BEFORE Flipping/Inverting: ";
cout << endl;
printLevelOrder(root);

cout << "Print Level Order for Tree 1 AFTER Flipping/Inverting: ";

cout << endl;
invert(root); // invert

cout << endl;

printLevelOrder(root);

cout << endl;

}
``````

Output:

``````Print Level Order for Tree 1 BEFORE Flipping/Inverting:
20
12 40
35 52
48 60
Print Level Order for Tree 1 AFTER Flipping/Inverting:
20
40 12
52 35
60 48
``````

## Same Tree Problem

• Problem: Pass in two trees into function and check if they’re the same tree!!

Approach

``````
``````

Code:

``````
``````

Output

``````
``````

Updated: