Problem Solving Related To Binary Search And AVL Tree

Balancing a Binary Search Tree

Write three rotation functions that help in transforming an unbalanced Binary Tree to

a Balanced Binary Tree.

Node* rotateLeft(Node *node);
Node* rotateRight(Node *node);
Node* rotateLeftRight(Node *node);

These functions will take a node at which point you should perform the respective rotations for the unbalanced tree and return the new root. 

The left right rotation should be performed as a left rotation on node's left child, then a right rotation on node.

We have defined the following C++ Node class for you.  The name serves as the value.

class Node
{
public:
std::string name;
Node* left = NULL;
Node* right = NULL;
};

Test Cases

• The first line of input in test cases is the number of nodes in the tree.

• The second line is the nodes of a tree which are inserted into a binary search tree in that order.

• You don't need to implement insert. You have access to the root of the constructed

• Binary Search Tree.

• We will create the tree for you, then call rotateLeftRight on the root of the tree. This is followed by a call to pre, in, and post-order traversal.

• The output is an pre, in, post-order traversal of the tree after the rotation separated by spaces.

Author: Cheryl Resch, Hamish Pierpont, Ori Leibovici and Amanpreet Kapoor, Date Created: May 2018, Last Modified: 26 Sep 2020

Sample Input:

3

2 0 1

Sample Output:

102 012 021

Write a program, test using stdin → stdout

#include<iostream>
#include<string>

class Node
{
public:
int name;
Node* left = NULL;
Node* right = NULL;
};

Node* insert(Node* root, int key)
{
if(root==NULL)
{
Node* temp=new Node();
temp-&gt;name=key;
return temp;
}
if (key &lt; root-&gt;name)
root-&gt;left = insert(root-&gt;left, key);
else if (key &gt; root-&gt;name)
root-&gt;right = insert(root-&gt;right, key);

return root;
}

std::string traverse(Node* head)
{
std::string string1, string2, string3;

if (head == NULL)
return &quot;&quot;;

string1 = traverse(head-&gt;left);
string2 = std::to_string(head-&gt;name);
string3 = traverse(head-&gt;right);

return string1+string2+string3;
}

Node* rotateLeft(Node *node)
{
//your code here
}

Node* rotateRight(Node *node)
{
//your code here
}

Node* rotateLeftRight(Node *node)
{
//your code here
}

int main()
{
Node* root=NULL;
int x;
int num;
std::cin &gt;&gt; num;
for(int i=0;i&lt;num;i++)
{
std::cin&gt;&gt;x;

root=insert(root,x);

}

root=rotateLeftRight(root);
std::cout &lt;&lt; traverse(root);
}

BST = AVL ?

Problem Statement

AVL Tree is a Binary Search Tree that allows Balance Factor of each node to be in the range -1 to 1 (n>=0). Implement a function that takes as input a root node of a Binary Search Tree. This function checks if the BST is an AVL Tree or not.

We have defined the following C++ Node class for you:

class Node
{
    public:
        int name;
        Node* left = NULL;
        Node* right = NULL;
};

Function to code

bool isAVL(Node* root);

Example

Inserted Numbers in a BST: -  5 2 15 16 9 11 14 ;

Tree:- 5

/ \

2 15

/ \

9 16

\

11

\

14

Balance Factor of tree = left subtree height – right subtree height = -3

Therefore, this BST is not an AVL Tree.

Test Cases

The input in test cases are nodes of a tree which are inserted in that order. You don't need to implement insert. You have access to the root of the constructed Binary Search Tree. Return true if the BST is a valid AVL Tree and False if not.

Hint: Use a Height function to calculate height of a tree at given node.

Author: Amanpreet Kapoor, Date Created: May 2018, Last Modified: 31 May 2020

Sample Input 1:

5 2 15 16 9 11 14

Sample Output 1:

false

Sample Input 2:

1 2 3

Sample Output 2:

false

Contact Us to get instant help related to C++, Data Structure Algorithms, etc., at:

contact@codersarts.com