Task 1 Each node in a binary tree contains an integer value and two pointers to next-level nodes: “left” and “right”. Write a function that takes a pointer to a root of a tree and checks whether the tree is sorted. Task 2 There is a 3D point and a line segment (bounded 3D line) given by endpoints. (..)write a function that will compute the dista…

AutodeskTasks.cpp

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iomanip>

using namespace std;

struct Tree{
	int val;
	Tree * up;
	Tree * left;
	Tree * right;
};

//printing BFS Inorder (from lowest value to highest)
void printTree(Tree * tree){
	if (tree){
		printTree(tree->left);
		cout << tree->val << " ";
		printTree(tree->right);
	}
}

void addLeaf(Tree *& root, Tree *& leaf){
	if (root == NULL){
		root = leaf;
		return;
	}
	if (leaf->val <= root->val){
		if (root->left){
			addLeaf(root->left, leaf);
		}
		else{
			root->left = leaf;
			leaf->up = root;
		}
	}
	else{
		if (root->right){
			addLeaf(root->right, leaf);
		}
		else{
			root->right = leaf;
			leaf->up = root;
		}
	}
}


void addLeafWrong(Tree *& root, Tree *& leaf){
	if (root == NULL){
		root = leaf;
		return;

	}
	if (leaf->val >= root->val){
		if (root->left){
			addLeafWrong(root->left, leaf);
		}
		else{
			root->left = leaf;
			leaf->up = root;
		}
	}
	else{
		if (root->right){
			addLeafWrong(root->right, leaf);
		}
		else{
			root->right = leaf;
			leaf->up = root;
		}
	}
}

void addNumber(Tree *& root, int nval){
	Tree * leaf = new Tree;
	leaf->left = leaf->right = leaf->up = NULL;
	leaf->val = nval;

	addLeaf(root, leaf);
}


void addNumberWrong(Tree *& root, int nval){
	Tree * leaf = new Tree;
	leaf->left = leaf->right = leaf->up = NULL;
	leaf->val = nval;

	addLeafWrong(root, leaf);
}

bool isSorted(Tree * tree){
	if (tree == NULL)return false;
	bool leftOk = false;
	bool rightOk = false;

	if (tree->left == NULL) leftOk = true;
	else if (isSorted(tree->left) & tree->left->val <= tree->val) leftOk = true;
	if (tree->right == NULL & leftOk) return  true;
	else if (tree->right){ 
		if (isSorted(tree->right) & tree->right->val > tree->val & leftOk) return true; 
	}
	return false;
}

struct Point{
	double X;
	double Y;
	double Z;
	Point(double x, double y, double z) : X(x), Y(y), Z(z){}
	void printMe(){
		cout << X << " " << Y << " " << Z << endl;
	}
};
struct Vector{
	double X;
	double Y;
	double Z;
	Vector(double x, double y, double z) : X(x), Y(y), Z(z){}
	Vector(Point A, Point B) {
		X = B.X - A.X;
		Y = B.Y - A.Y;
		Z = B.Z - A.Z;
	}
	void printMe(){
		cout << X << " " << Y << " " << Z << endl;
	}
};
double vecLen(Vector v){
	return sqrt((v.X)*(v.X) + (v.Y)*(v.Y) + (v.Z)*(v.Z));
}

Vector vecCross(Vector v1, Vector v2){
	Vector v = Vector((v1.Y*v2.Z) - (v1.Z*v2.Y), (v1.X*v2.Z) - (v1.Z*v2.X), (v1.X*v2.Y) - (v1.Y*v2.X));
	return v;
}
double vecDot(Vector v1, Vector v2){
	return (v1.X*v2.X) + (v1.Y*v2.Y) + (v1.Z*v2.Z);
}
double vecSum(Vector v1, Vector v2){
	return vecLen(v1)+vecLen(v2);
}


double calcualteDistance(Point A, Point B, Point P){
	double distance = 0.0;
	Vector base = Vector(A, B);
	Vector baseReversed = Vector(B, A);
	Vector vAP = Vector(A, P);
	Vector vBP = Vector(B, P);
	double alpha = acos(vecDot(base, vAP) / (vecSum(base, vAP)))*(180.0 / 3.14);
	double beta = acos(vecDot(baseReversed, vBP) / (vecSum(baseReversed, vBP)))*(180.0 / 3.14);
	if (alpha > 90 || beta > 90){
		if (vecLen(vAP) < vecLen(vBP))return vecLen(vAP);
		else return vecLen(vBP);
	}
	return vecLen(vecCross(vAP, base))/vecLen(base);
}

int ** fillSpiralMatrix(int ** &matrix, int N, int iteration){
	if (iteration * 2 >= N)return matrix;
	int currentMatrixSize = N - (2 * iteration);
	int currentLastRow = N-1 - iteration;
	int startingNumber = (N*N) - (currentMatrixSize*currentMatrixSize)+1;

	//top side of matrix
	for (int i = 0; i < currentMatrixSize; i++){
		matrix[iteration][iteration + i] = startingNumber;
		startingNumber++;
	}

	//left side
	//top kind of cuts into 1 number from "left side" in order to make sure that when N=1 then exacly one "for" will work.
	for (int i = 0; i < currentMatrixSize - 2; i++){
		matrix[iteration + 1 + i][currentLastRow] = startingNumber;		 
		startingNumber++;
	}

	//bottom
	for (int i = 0; i < currentMatrixSize-1; i++){
		matrix[currentLastRow][currentLastRow - i] = startingNumber;
		startingNumber++;
	}
	
	//right
	for (int i = 0; i < currentMatrixSize - 1; i++){
		matrix[currentLastRow - i][iteration] = startingNumber;
		startingNumber++;
	}

	return fillSpiralMatrix(matrix, N, iteration + 1);
}

void printMatrixNxN(int ** matrix, int N){
	
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){

			cout << std::setw(3) <<matrix[i][j] << " ";
		}
		cout << endl;
	}
}

int main(){
	srand(time(NULL));
	cout << "Check if a BST tree is sorted:" << endl;
	Tree * tree = NULL;
	for (int i = 0; i < 20; i++)addNumber(tree, rand() % 30);
	printTree(tree);

	if (isSorted(tree)) cout << "Sorted;" << endl;
	else cout << "Not sorted." << endl;

	addNumberWrong(tree, 666);
	printTree(tree);
	if (isSorted(tree)) cout << "Sorted;" << endl;
	else cout << "Not sorted." << endl;
 
	cout <<endl<< "Calculate the distance from line AB to P" << endl;

	Point A = Point(4, 2, 5);
	Point B = Point(4, 5, 3);
	Point P = Point(6, 8, 5);
	Vector base = Vector(A, B);
	Vector vAP = Vector(A, P);
	Vector vBP = Vector(B, P);
	cout << "Point A: ";
	A.printMe();
	cout << "Point B: ";
	B.printMe();
	cout << "Point P: ";
	P.printMe();
	cout << "Lengths: " << vecLen(base) << " " << vecLen(vAP) << " " << vecLen(vBP) << " "<<endl;
	cout << endl << "The distance is the length of a vector AP: " << calcualteDistance(A, B, P) << endl;

	Point A2 = Point(0, 0, 0);
	Point B2 = Point(10, 10, 10);
	Point P2 = Point(5, 5, 5);
	cout << "Point A2: ";
	A.printMe();
	cout << "Point B2: ";
	B.printMe();
	cout << "Point P2: ";
	P.printMe();
	cout << endl << "Point is collinear. The distance is: " << calcualteDistance(A2, B2, P2) << endl;



	Point A3 = Point(0, 0, 0);
	Point B3 = Point(10, 10, 10);
	Point P3 = Point(3, 7, 5);
	Vector base3 = Vector(A3, B3);
	Vector vAP3 = Vector(A3, P3);
	Vector vBP3 = Vector(B3, P3);
	cout << "Point A3: ";
	A.printMe();
	cout << "Point B3: ";
	B.printMe();
	cout << "Point P3: ";
	P.printMe();
	cout << "Lengths: " << vecLen(base3) << " " << vecLen(vAP3) << " " << vecLen(vBP3) << " " << endl;
	cout <<endl<< "The distance is the \"height\": " << calcualteDistance(A3, B3, P3) << endl;


	
	int N = rand() % 20 + 1;
	int ** matrix = new int*[N];
	for (int i = 0; i < N; i++){
		matrix[i] = new int[N];
	}
	cout<<endl << "Printing a NxN spiral matrix where N = " << N<<endl<<endl;
	matrix = fillSpiralMatrix(matrix, N, 0);

	printMatrixNxN(matrix,N);

	system("Pause");

}