A binary tree is a tree which is characterized by any one of the following properties:
Inorder traversal is performed as
We define depth of a node as follow:
Eg. In the following tree, we swap children of node
Swap operation: Given a tree and a integer,
You are given a tree of
Input Format
First line of input contains
Next line contain an integer,
Output Format
For each
Constraints
1 <= N <= 1024
1 <= T <= 100
1 <= K <= N
Either a = -1 or 2 <= a <= N
Either b = -1 or 2 <= b <= N
Index of (non-null) child will always be greater than that of parent.
Sample Input #00
**
Test Case #00: As node 2 and 3 has no child, swapping will not have any effect on it. We only have to swap the child nodes of root node.
- It can be an empty (null).
- It contains a root node and two subtrees, left subtree and right subtree. These subtrees are also binary tree.
Swap Nodes [Algo] - Hacker Rank Solution
Inorder traversal is performed as
- Traverse the left subtree.
- Visit root (print it).
- Traverse the right subtree.
We define depth of a node as follow:
- Root node is at depth 1.
- If the depth of parent node is
d, then the depth of current node wll bed+1.
L and right subtree R, then after swapping left subtree will be R and right subtree L.Eg. In the following tree, we swap children of node
1. Depth
1 1 [1]
/ \ / \
2 3 -> 3 2 [2]
\ \ \ \
4 5 5 4 [3]
2 4 1 3 5 and of right tree is 3 5 1 2 4.Swap operation: Given a tree and a integer,
K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...].You are given a tree of
N nodes where nodes are indexed from [1..N] and it is rooted at 1. You have to perform T swap operations on it, and after each swap operation print the inorder traversal of the current state of the tree.Input Format
First line of input contains
N, number of nodes in tree. Then N lines follow. Here each of ith line (1 <= i <= N) contains two integers, a b, where a is the index of left child, and b is the index of right child of ith node. -1 is used to represent null node. Next line contain an integer,
T. Then again T lines follows. Each of these line contains an integer K.Output Format
For each
K, perform swap operation as mentioned above and print the inorder traversal of the current state of tree.Constraints
1 <= N <= 1024
1 <= T <= 100
1 <= K <= N
Either a = -1 or 2 <= a <= N
Either b = -1 or 2 <= b <= N
Index of (non-null) child will always be greater than that of parent.
Sample Input #00
3
2 3
-1 -1
-1 -1
2
1
1
3 1 2
2 1 3
5
2 3
-1 4
-1 5
-1 -1
-1 -1
1
2
4 2 1 5 3
11
2 3
4 -1
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4
2 9 6 4 1 3 7 5 11 8 10
2 6 9 4 1 3 7 5 10 8 11
**
[s] represents swap operation is done at this depth.Test Case #00: As node 2 and 3 has no child, swapping will not have any effect on it. We only have to swap the child nodes of root node.
1 [s] 1 [s] 1
/ \ -> / \ -> / \
2 3 [s] 3 2 [s] 2 3
1 1
/ \ / \
2 3 [s] -> 2 3
\ \ / /
4 5 4 5
1 1 1
/ \ / \ / \
/ \ / \ / \
2 3 [s] 2 3 2 3
/ / \ \ \ \
/ / \ \ \ \
4 5 -> 4 5 -> 4 5
/ / \ / / \ / / \
/ / \ / / \ / / \
6 7 8 [s] 6 7 8 [s] 6 7 8
\ / \ / / \ \ / \
\ / \ / / \ \ / \
9 10 11 9 11 10 9 10 11 ----------------------------------------------------------------------------- Swap Nodes [Algo] code
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Node {
int data;
public:
Node * children[2];
Node();
Node(int);
~Node();
void setData(int);
int getData();
};
Node::Node(){
children[0] = NULL;
children[1] = NULL;
}
Node::Node(int _data){
data = _data;
children[0] = NULL;
children[1] = NULL;
}
Node::~Node(){
for(int i = 0; i < 2; i++){
if(children[i] != NULL){
delete(children[i]);
}
children[i] = NULL;
}
}
void Node::setData(int _data){
data = _data;
}
int Node::getData(){
return data;
}
class Tree {
Node * root;
void swapNodesLevel(Node **,int,int);
void printPreorder(Node *);
void printInOrder(Node *);
public:
Tree();
void addChildPair(int,int,int);
void print();
void swapNodes(int);
};
Tree::Tree(){
root = new Node(1);
}
void Tree::addChildPair(int left, int right, int pos){
vector<Node *> queue;
Node * ptr;
queue.push_back(root);
while(queue.size() > 0){
ptr = queue[0];
if(pos == 0){
if(left == -1){
ptr->children[0] = NULL;
} else {
ptr->children[0] = new Node(left);
}
if(right == -1){
ptr->children[1] = NULL;
} else {
ptr->children[1] = new Node(right);
}
break;
}
queue.erase(queue.begin());
for(int i = 0; i < 2; i++){
if(ptr->children[i] != NULL){
queue.push_back(ptr->children[i]);
}
}
pos--;
}
}
void Tree::print(){
printInOrder(root);
cout << endl;
}
void Tree::printPreorder(Node * ptr){
cout << ptr->getData() << " ";
if(ptr->children[0] != NULL){
printPreorder(ptr->children[0]);
}
if(ptr->children[1] != NULL){
printPreorder(ptr->children[1]);
}
}
void Tree::printInOrder(Node * ptr){
if(ptr->children[0] != NULL){
printInOrder(ptr->children[0]);
}
cout << ptr->getData() << " ";
if(ptr->children[1] != NULL){
printInOrder(ptr->children[1]);
}
}
void Tree::swapNodes(int depth){
swapNodesLevel(&root,depth,1);
}
void Tree::swapNodesLevel(Node ** ptr,int depth,int current){
if(current % depth == 0){
Node * temp = (*ptr)->children[0];
(*ptr)->children[0] = (*ptr)->children[1];
(*ptr)->children[1] = temp;
}
for(int i = 0; i < 2; i++){
if((*ptr)->children[i] != NULL){
swapNodesLevel(&((*ptr)->children[i]),depth,current+1);
}
}
}
int main() {
int nodes; cin >> nodes;
int a, b;
Tree * mytree = new Tree();
for(int i = 0; i < nodes; i++){
cin >> a >> b;
mytree->addChildPair(a,b,i);
}
cin >> a;
while(a--){
cin >> b;
mytree->swapNodes(b);
mytree->print();
}
return 0;
}----------------------------------------------------------------------------------
Swap Nodes [Algo] - Hacker rank solution