We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Data Structures
- Trees
- Swap Nodes [Algo]
- Discussions
Swap Nodes [Algo]
Swap Nodes [Algo]
Sort by
recency
|
718 Discussions
|
Please Login in order to post a comment
Java Solution, using level order traversal using 2 queues Start with putting 1 in the primary queue, 1. poll from primary queue, check if you need to swap the child i.e level % k == 0. 2. add the child indexes in secondary queuue. repeat step 1 and 2 until primary queue is empty. once empty means level is done, go to next level. poll all the indexes from secondary and add into primary. do the inOrderTraversal of the tree and add the list to a list
public static List> swapNodes(List> indexes, List queries) { // Write your code here Queue primary = new LinkedList<>(); Queue secondary = new LinkedList<>();
include
include
include
include
include
using namespace std; vector leftNode, rightNode; int swapLevel;
void traverse(int node=1){ if (node == -1) return; traverse(leftNode[node]); cout << node << " "; traverse(rightNode[node]); if (node == 1) cout << endl; }
void swap(int level=1, int node=1) { if (node == -1) return; if (level % swapLevel == 0) { int tmp = leftNode[node]; leftNode[node] = rightNode[node]; rightNode[node] = tmp; } swap(level+1, leftNode[node]); swap(level+1, rightNode[node]); }
int main() { int count;
cin>>count; leftNode.push_back(0); rightNode.push_back(0); while(count--){ int L, R; cin>>L>>R; leftNode.push_back(L); rightNode.push_back(R); } cin>>count; while(count--){ cin >> swapLevel; swap(); traverse(); } return 0; }
SOLUTION
include
include
struct node { int id; int depth; struct node *left, *right; };
void inorder(struct node* tree) { if(tree == NULL) return;
}
int main(void) { int no_of_nodes, i = 0; int l,r, max_depth,k; struct node* temp = NULL; scanf("%d",&no_of_nodes); struct node* tree = (struct node *) calloc(no_of_nodes , sizeof(struct node)); tree[0].depth = 1; while(i < no_of_nodes ) { tree[i].id = i+1; scanf("%d %d",&l,&r); if(l == -1) tree[i].left = NULL; else { tree[i].left = &tree[l-1]; tree[i].left->depth = tree[i].depth + 1; max_depth = tree[i].left->depth; }
}
SOLUTION
include
include
struct node { int id; int depth; struct node *left, *right; };
void inorder(struct node* tree) { if(tree == NULL) return;
}
int main(void) { int no_of_nodes, i = 0; int l,r, max_depth,k; struct node* temp = NULL; scanf("%d",&no_of_nodes); struct node* tree = (struct node *) calloc(no_of_nodes , sizeof(struct node)); tree[0].depth = 1; while(i < no_of_nodes ) { tree[i].id = i+1; scanf("%d %d",&l,&r); if(l == -1) tree[i].left = NULL; else { tree[i].left = &tree[l-1]; tree[i].left->depth = tree[i].depth + 1; max_depth = tree[i].left->depth; }
}