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

Contact Us

Tel: (+91) 0120  4118730  

Time :   10 : 00  AM -  08 : 00 PM IST 

Registered address: G-69, Sector 63, 

 Noida - 201301, India

We Provide Services Across The different countries

USA    Australia   Canada   UK    UAE    Singapore   New Zealand    Malasia   India   Ireland   Germany

CodersArts is a Product by Sofstack Technology Solutions Pvt. Ltd.

  • CodersArts | Linkedin
  • Instagram