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

Max Path Sum

kNth Smallest