Given a binary tree, we need to write a program to swap leaf nodes in the given binary tree pairwise starting from left to right as shown below.
Tree before swapping:
Tree after swapping:
The sequence of leaf nodes in original binary tree from left to right is (4, 6, 7, 9, 10). Now if we try to form pairs from this sequence, we will have two pairs as (4, 6), (7, 9). The last node (10) is unable to form pair with any node and thus left unswapped.
The idea to solve this problem is to first traverse the leaf nodes of the binary tree from left to right. While traversing the leaf nodes, we maintain two pointers to keep track of first and second leaf nodes in a pair and a variable count to keep track of count of leaf nodes traversed. Now, if we observe carefully then we see that while traversing if the count of leaf nodes traversed is even, it means that we can form a pair of leaf nodes. To keep track of this pair we take two pointers firstPtr and secondPtr as mentioned above. Every time we encounter a leaf node we initialize secondPtr with this leaf node. Now if the count is odd, we initialize firstPtr with secondPtr otherwise we simply swap these two nodes.
Below is the C++ implementation of above idea:
CPP
/* C++ program to pairwise swap leaf nodes from left to right */#include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int data; struct Node *left, *right; }; // function to swap two Node void Swap(Node **a, Node **b) { Node * temp = *a; *a = *b; *b = temp; } // two pointers to keep track of // first and second nodes in a pair Node **firstPtr; Node **secondPtr; // function to pairwise swap leaf // nodes from left to right void pairwiseSwap(Node **root, int &count) { // if node is null, return if (!(*root)) return; // if node is leaf node, increment count if(!(*root)->left&&!(*root)->right) { // initialize second pointer // by current node secondPtr = root; // increment count count++; // if count is even, swap first // and second pointers if (count%2 == 0) Swap(firstPtr, secondPtr); else // if count is odd, initialize // first pointer by second pointer firstPtr = secondPtr; } // if left child exists, check for leaf // recursively if ((*root)->left) pairwiseSwap(&(*root)->left, count); // if right child exists, check for leaf // recursively if ((*root)->right) pairwiseSwap(&(*root)->right, count); } // Utility function to create a new tree node Node* newNode(int data) { Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // function to print inorder traversal // of binary tree void printInorder(Node* node) { if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ printf("%d ", node->data); /* now recur on right child */ printInorder(node->right); } // Driver program to test above functions int main() { // Let us create binary tree shown in // above diagram Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->right->left = newNode(5); root->right->right = newNode(8); root->right->left->left = newNode(6); root->right->left->right = newNode(7); root->right->right->left = newNode(9); root->right->right->right = newNode(10); // print inorder traversal before swapping cout << "Inorder traversal before swap:\n"; printInorder(root); cout << "\n"; // variable to keep track // of leafs traversed int c = 0; // Pairwise swap of leaf nodes pairwiseSwap(&root, c); // print inorder traversal after swapping cout << "Inorder traversal after swap:\n"; printInorder(root); cout << "\n"; return 0; } |
Java
/* Java program to pairwise swap leaf nodes from left to right */// A binary Tree Node class Node { int data; Node left, right; Node(int data) { this.data = data; left = null; right = null; } } class Main { // two pointers to keep track of // first and second nodes in a pair static Node firstPtr = null; static Node secondPtr = null; // variable to keep track // of leafs traversed static int count = 0; // function to pairwise swap leaf // nodes from left to right public static void pairWiseSwap(Node root) { // if node is null, return if (root == null) return; // if node is leaf node, increment count if (root.left == null && root.right == null) { // initialize second pointer // by current node secondPtr = root; // increment count count++; // if count is even, swap first // and second pointers if (count % 2 == 0) { int temp = firstPtr.data; firstPtr.data = secondPtr.data; secondPtr.data = temp; } // if count is odd, initialize // first pointer by second pointer else firstPtr = secondPtr; } // if left child exists, check for leaf // recursively if (root.left != null) pairWiseSwap(root.left); // if right child exists, check for leaf // recursively if (root.right != null) pairWiseSwap(root.right); } // Utility function to create a new tree node public static Node newNode(int data) { return new Node(data); } // function to print inorder traversal // of binary tree public static void printInorder(Node node) { if (node == null) return; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ System.out.print(node.data + " "); /* now recur on right child */ printInorder(node.right); } // Driver program to test above functions public static void main(String[] args) { // Let us create binary tree shown in // above diagram Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(8); root.right.left.left = newNode(6); root.right.left.right = newNode(7); root.right.right.left = newNode(9); root.right.right.right = newNode(10); // print inorder traversal before swapping System.out.print( "Inorder traversal before swap : "); printInorder(root); pairWiseSwap(root); // print inorder traversal after swapping System.out.println(); System.out.print("Inorder traversal after swap: "); printInorder(root); } } |
Python3
# Python program to pairwise swap # leaf nodes from left to right # a binary tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # function to swap two node def Swap(a, b): temp = a.data a.data = b.data b.data = temp # two pointers to keep track of # first and second nodes in pair firstPtr = NonesecondPtr = None # functiont o pairwise swap leaf # nodes from left to right count = 0def pairwiseSwap(root): # if node is null, return if(root is None): return # if node is leaf node, incrrement count if(root.left is None and root.right is None): global count, firstPtr, secondPtr # initialize second pointer by current node secondPtr = root # increment count count += 1 # if count is even, swap first # and second pointers if(count % 2 == 0): Swap(firstPtr, secondPtr) else: # if count is odd, initialize # first pointer by second pointer firstPtr = secondPtr # if left child exists, check for leaf # recursively if(root.left is not None): pairwiseSwap(root.left) # if right child exists, check for leaf # recursively if(root.right is not None): pairwiseSwap(root.right) # utility function to create a new node def newNode(data): return Node(data) # function to print inorder traversal of binary tree def printInorder(node): if(node is None): return # first recur on left child printInorder(node.left) # then print the data of node print(node.data, end=" ") # now recur on right child printInorder(node.right) # driver program to test above function # let us create a binary tree shownin above diagram root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.right.left = newNode(5) root.right.right = newNode(8) root.right.left.left = newNode(6) root.right.left.right = newNode(7) root.right.right.left = newNode(9) root.right.right.right = newNode(10) # print Inorder traversal before swapping print("Inorder traversal before swap : ") printInorder(root) # variable to keep track of leafs traversed # pairwise swap of leaf nodes pairwiseSwap(root) # print Inorder traversal after swapping print("\nInorder traversal after swap : ") printInorder(root) |
C#
// C# Program to pairwise swap // leaf nodes from left to right // in a binary tree node using System; public class Node{ public int data; public Node left, right; public Node(int item){ data = item; left = right = null; } } public class BinaryTree{ static Node firstPtr; static Node secondPtr; // function to swap two node static void Swap(Node a, Node b){ int temp = a.data; a.data = b.data; b.data = temp; } // function to pairwise swap leaf // nodes from left to right static int count = 0; static void pairwiseSwap(Node root){ // if node is null, return if(root == null) return; // if node is leaf node, increment count if(root.left == null && root.right == null){ // initialize second pointer by current node secondPtr = root; // increment count count += 1; // if count is even, swap first // and second pointers if(count % 2 == 0){ Swap(firstPtr, secondPtr); }else{ // if count is odd, initialize // first pointer by second pointer firstPtr = secondPtr; } } // if left child exists, check for leaf // recursively if(root.left != null){ pairwiseSwap(root.left); } // if right child exists, check for leaf // recursively if(root.right != null){ pairwiseSwap(root.right); } } // utility function to create a new tree node static Node newNode(int data){ return new Node(data); } // function to print inorder traversal of binary tree static void printInorder(Node node){ if(node == null) return; // first recur on left child printInorder(node.left); // then print the data of node Console.Write(node.data + " "); // now recur on right child printInorder(node.right); } // driver program to test above function static public void Main (){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(8); root.right.left.left = newNode(6); root.right.left.right = newNode(7); root.right.right.left = newNode(9); root.right.right.right = newNode(10); // print inorder traversal before swapping Console.WriteLine("Inorder Traversal before swap : "); printInorder(root); Console.WriteLine(); // variable to keep track of leafs traversal // pairwise swap of leaf nodes pairwiseSwap(root); // print inorder traversal after swapping Console.WriteLine("Inorder traversal after swap : "); printInorder(root); } } // this code is contributed by Kirti Agarwal(kirtiagarwal23121999) |
Javascript
// JavaScript program to pairwise swap leaf // nodes from left to right // a binary tree node class Node{ constructor(data){ this.data = data; this.left = null; this.right = null; } } // function to swap two node function Swap(a, b){ let temp = a.data; a.data = b.data; b.data = temp; } // two pointers to keep track of // first and second nodes in pair let firstPrt; let secondPtr; // function to pairwise swap leaf // nodes from left to right let count = 0; function pairwiseSwap(root) { // if node is null, return if(root == null) return; // if node is leaf node, increment count if(root.left == null && root.right == null){ // initialize second pointer by current node secondPtr = root; // increment count count++; // if count is even, swap first // and second pointers if(count % 2 == 0){ Swap(firstPtr, secondPtr); } else{ // if count is odd, initialize // first pointer by second pointer firstPtr = secondPtr; } } // if left child exists, check for leaf // recursively if(root.left != null){ pairwiseSwap(root.left); } // if right child exists, check for leaf // recursively if(root.right != null){ pairwiseSwap(root.right); } } // utility function to create a new tree node function newNode(data){ return new Node(data); } // function to print inorder traversal of bianry tree function printInorder(node){ if(node == null) return; // first recur on left child printInorder(node.left); // then print the data of node console.log(node.data + " "); // now recur on right child printInorder(node.right); } // driver program to test above functions // let us create binary tree shown in above diagram let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(8); root.right.left.left = newNode(6); root.right.left.right = newNode(7); root.right.right.left = newNode(9); root.right.right.right = newNode(10); // print inorder traversal before swapping console.log("Inorder traversal before swap: "); printInorder(root); // variable to keep track of leafs traversed // pairwise swap of leaf nodes pairwiseSwap(root); // print inorder traversal after swapping console.log("Inorder traversal after swap: "); printInorder(root); // this code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(n)
This article is contributed by Harsh Agarwal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
