Pairwise swap leaf nodes in a binary tree

Here given code implementation process.
/*
C Program
Pairwise swap leaf nodes in a binary tree
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// returns a new node of tree
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
// Swap the value of given nodes values
void swapValue(struct TreeNode *a, struct TreeNode *b)
{
int temp = a->data;
a->data = b->data;
b->data = temp;
}
// Swap leaf node elements in pairwise manner
void swapLeafPair(struct TreeNode *node, struct TreeNode **prev)
{
if (node != NULL)
{
if (node->left == NULL && node->right == NULL)
{
if ( *prev == NULL)
{
// First pair node
*prev = node;
}
else
{
swapValue(node, *prev);
// Reset pair element
*prev = NULL;
}
return;
}
// Recursively visiting left and right subtree
swapLeafPair(node->left, prev);
swapLeafPair(node->right, prev);
}
}
// Handles the request of swapping leaf nodes
void swapLeafNodes(struct TreeNode *root)
{
if (root == NULL)
{
printf("\n Empty Tree \n");
return;
}
struct TreeNode *prev = NULL;
swapLeafPair(root, & prev);
}
//Display Inorder view of binary tree
void inorder(struct TreeNode *node)
{
if (node)
{
inorder(node->left);
//Print node value
printf(" %d", node->data);
inorder(node->right);
}
}
int main(int argc, char
const *argv[])
{
struct BinaryTree *tree = newTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree->root = newNode(1);
tree->root->left = newNode(2);
tree->root->right = newNode(8);
tree->root->left->left = newNode(3);
tree->root->left->right = newNode(10);
tree->root->left->right->left = newNode(7);
tree->root->right->left = newNode(6);
tree->root->right->left->right = newNode(9);
tree->root->right->right = newNode(4);
tree->root->right->left->left = newNode(5);
tree->root->right->right->right = newNode(11);
tree->root->right->right->right->left = newNode(12);
tree->root->right->right->right->right = newNode(13);
inorder(tree->root);
swapLeafNodes(tree->root);
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
printf("\n After Swap Leaf nodes \n");
inorder(tree->root);
return 0;
}
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
/*
Java Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public TreeNode prev;
public BinaryTree()
{
this.root = null;
this.prev = null;
}
// Swap the value of given nodes values
public void swapValue(TreeNode a, TreeNode b)
{
int temp = a.data;
a.data = b.data;
b.data = temp;
}
// Swap leaf node elements in pairwise manner
public void swapLeafPair(TreeNode node)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
if (this.prev == null)
{
// First pair node
this.prev = node;
}
else
{
swapValue(node, this.prev);
// Reset pair element
this.prev = null;
}
return;
}
// Recursively visiting left and right subtree
swapLeafPair(node.left);
swapLeafPair(node.right);
}
}
// Handles the request of swapping leaf nodes
public void swapLeafNodes()
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
return;
}
this.prev = null;
swapLeafPair(this.root);
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
//Print node value
System.out.print(" " + node.data);
inorder(node.right);
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
System.out.print("\n After Swap Leaf nodes \n");
tree.inorder(tree.root);
}
}
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Define Binary Tree
class BinaryTree
{
public: TreeNode *root;
TreeNode *prev;
BinaryTree()
{
this->root = NULL;
this->prev = NULL;
}
// Swap the value of given nodes values
void swapValue(TreeNode *a, TreeNode *b)
{
int temp = a->data;
a->data = b->data;
b->data = temp;
}
// Swap leaf node elements in pairwise manner
void swapLeafPair(TreeNode *node)
{
if (node != NULL)
{
if (node->left == NULL && node->right == NULL)
{
if (this->prev == NULL)
{
// First pair node
this->prev = node;
}
else
{
this->swapValue(node, this->prev);
// Reset pair element
this->prev = NULL;
}
return;
}
// Recursively visiting left and right subtree
this->swapLeafPair(node->left);
this->swapLeafPair(node->right);
}
}
// Handles the request of swapping leaf nodes
void swapLeafNodes()
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
return;
}
this->prev = NULL;
this->swapLeafPair(this->root);
}
//Display Inorder view of binary tree
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
//Print node value
cout << " " << node->data;
this->inorder(node->right);
}
}
};
int main()
{
BinaryTree tree = BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(8);
tree.root->left->left = new TreeNode(3);
tree.root->left->right = new TreeNode(10);
tree.root->left->right->left = new TreeNode(7);
tree.root->right->left = new TreeNode(6);
tree.root->right->left->right = new TreeNode(9);
tree.root->right->right = new TreeNode(4);
tree.root->right->left->left = new TreeNode(5);
tree.root->right->right->right = new TreeNode(11);
tree.root->right->right->right->left = new TreeNode(12);
tree.root->right->right->right->right = new TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
cout << "\n After Swap Leaf nodes \n";
tree.inorder(tree.root);
return 0;
}
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
// Include namespace system
using System;
/*
C# Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public TreeNode prev;
public BinaryTree()
{
this.root = null;
this.prev = null;
}
// Swap the value of given nodes values
public void swapValue(TreeNode a, TreeNode b)
{
int temp = a.data;
a.data = b.data;
b.data = temp;
}
// Swap leaf node elements in pairwise manner
public void swapLeafPair(TreeNode node)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
if (this.prev == null)
{
// First pair node
this.prev = node;
}
else
{
swapValue(node, this.prev);
// Reset pair element
this.prev = null;
}
return;
}
// Recursively visiting left and right subtree
swapLeafPair(node.left);
swapLeafPair(node.right);
}
}
// Handles the request of swapping leaf nodes
public void swapLeafNodes()
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
return;
}
this.prev = null;
swapLeafPair(this.root);
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
//Print node value
Console.Write(" " + node.data);
inorder(node.right);
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
Console.Write("\n After Swap Leaf nodes \n");
tree.inorder(tree.root);
}
}
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
<?php
/*
Php Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
public $prev;
function __construct()
{
$this->root = null;
$this->prev = null;
}
// Swap the value of given nodes values
public function swapValue($a, $b)
{
$temp = $a->data;
$a->data = $b->data;
$b->data = $temp;
}
// Swap leaf node elements in pairwise manner
public function swapLeafPair($node)
{
if ($node != null)
{
if ($node->left == null && $node->right == null)
{
if ($this->prev == null)
{
// First pair node
$this->prev = $node;
}
else
{
$this->swapValue($node, $this->prev);
// Reset pair element
$this->prev = null;
}
return;
}
// Recursively visiting left and right subtree
$this->swapLeafPair($node->left);
$this->swapLeafPair($node->right);
}
}
// Handles the request of swapping leaf nodes
public function swapLeafNodes()
{
if ($this->root == null)
{
echo "\n Empty Tree \n";
return;
}
$this->prev = null;
$this->swapLeafPair($this->root);
}
//Display Inorder view of binary tree
public function inorder($node)
{
if ($node != null)
{
$this->inorder($node->left);
//Print node value
echo " ". $node->data;
$this->inorder($node->right);
}
}
}
function main()
{
$tree = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(3);
$tree->root->left->right = new TreeNode(10);
$tree->root->left->right->left = new TreeNode(7);
$tree->root->right->left = new TreeNode(6);
$tree->root->right->left->right = new TreeNode(9);
$tree->root->right->right = new TreeNode(4);
$tree->root->right->left->left = new TreeNode(5);
$tree->root->right->right->right = new TreeNode(11);
$tree->root->right->right->right->left = new TreeNode(12);
$tree->root->right->right->right->right = new TreeNode(13);
$tree->inorder($tree->root);
$tree->swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
echo "\n After Swap Leaf nodes \n";
$tree->inorder($tree->root);
}
main();
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
/*
Node Js Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
this.root = null;
this.prev = null;
}
// Swap the value of given nodes values
swapValue(a, b)
{
var temp = a.data;
a.data = b.data;
b.data = temp;
}
// Swap leaf node elements in pairwise manner
swapLeafPair(node)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
if (this.prev == null)
{
// First pair node
this.prev = node;
}
else
{
this.swapValue(node, this.prev);
// Reset pair element
this.prev = null;
}
return;
}
// Recursively visiting left and right subtree
this.swapLeafPair(node.left);
this.swapLeafPair(node.right);
}
}
// Handles the request of swapping leaf nodes
swapLeafNodes()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
return;
}
this.prev = null;
this.swapLeafPair(this.root);
}
//Display Inorder view of binary tree
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
//Print node value
process.stdout.write(" " + node.data);
this.inorder(node.right);
}
}
}
function main()
{
var tree = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
process.stdout.write("\n After Swap Leaf nodes \n");
tree.inorder(tree.root);
}
main();
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
# Python 3 Program
# Pairwise swap leaf nodes in a binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
self.root = None
self.prev = None
# Swap the value of given nodes values
def swapValue(self, a, b) :
temp = a.data
a.data = b.data
b.data = temp
# Swap leaf node elements in pairwise manner
def swapLeafPair(self, node) :
if (node != None) :
if (node.left == None and node.right == None) :
if (self.prev == None) :
# First pair node
self.prev = node
else :
self.swapValue(node, self.prev)
# Reset pair element
self.prev = None
return
# Recursively visiting left and right subtree
self.swapLeafPair(node.left)
self.swapLeafPair(node.right)
# Handles the request of swapping leaf nodes
def swapLeafNodes(self) :
if (self.root == None) :
print("\n Empty Tree ")
return
self.prev = None
self.swapLeafPair(self.root)
# Display Inorder view of binary tree
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.inorder(node.right)
def main() :
tree = BinaryTree()
#
# 1
# / \
# / \
# 2 8
# / \ / \
# 3 10 6 4
# / / \ \
# 7 5 9 11
# / \
# 12 13
# -----------------------
# Binary Tree
# -----------------------
#
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(8)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(10)
tree.root.left.right.left = TreeNode(7)
tree.root.right.left = TreeNode(6)
tree.root.right.left.right = TreeNode(9)
tree.root.right.right = TreeNode(4)
tree.root.right.left.left = TreeNode(5)
tree.root.right.right.right = TreeNode(11)
tree.root.right.right.right.left = TreeNode(12)
tree.root.right.right.right.right = TreeNode(13)
tree.inorder(tree.root)
tree.swapLeafNodes()
#
# 1
# / \
# / \
# 2 8
# / \ / \
# 7 10 6 4
# / / \ \
# 3 9 5 11
# / \
# 13 12
# -----------------------
# After swap leaf node pairs
# -----------------------
#
print("\n After Swap Leaf nodes ")
tree.inorder(tree.root)
if __name__ == "__main__": main()
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
# Ruby Program
# Pairwise swap leaf nodes in a binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Define Binary Tree
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :prev
attr_accessor :root, :prev
def initialize()
self.root = nil
self.prev = nil
end
# Swap the value of given nodes values
def swapValue(a, b)
temp = a.data
a.data = b.data
b.data = temp
end
# Swap leaf node elements in pairwise manner
def swapLeafPair(node)
if (node != nil)
if (node.left == nil && node.right == nil)
if (self.prev == nil)
# First pair node
self.prev = node
else
self.swapValue(node, self.prev)
# Reset pair element
self.prev = nil
end
return
end
# Recursively visiting left and right subtree
self.swapLeafPair(node.left)
self.swapLeafPair(node.right)
end
end
# Handles the request of swapping leaf nodes
def swapLeafNodes()
if (self.root == nil)
print("\n Empty Tree \n")
return
end
self.prev = nil
self.swapLeafPair(self.root)
end
# Display Inorder view of binary tree
def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print(" ", node.data)
self.inorder(node.right)
end
end
end
def main()
tree = BinaryTree.new()
#
# 1
# / \
# / \
# 2 8
# / \ / \
# 3 10 6 4
# / / \ \
# 7 5 9 11
# / \
# 12 13
# -----------------------
# Binary Tree
# -----------------------
#
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(10)
tree.root.left.right.left = TreeNode.new(7)
tree.root.right.left = TreeNode.new(6)
tree.root.right.left.right = TreeNode.new(9)
tree.root.right.right = TreeNode.new(4)
tree.root.right.left.left = TreeNode.new(5)
tree.root.right.right.right = TreeNode.new(11)
tree.root.right.right.right.left = TreeNode.new(12)
tree.root.right.right.right.right = TreeNode.new(13)
tree.inorder(tree.root)
tree.swapLeafNodes()
#
# 1
# / \
# / \
# 2 8
# / \ / \
# 7 10 6 4
# / / \ \
# 3 9 5 11
# / \
# 13 12
# -----------------------
# After swap leaf node pairs
# -----------------------
#
print("\n After Swap Leaf nodes \n")
tree.inorder(tree.root)
end
main()
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
/*
Scala Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode , var prev: TreeNode)
{
def this()
{
this(null, null);
}
// Swap the value of given nodes values
def swapValue(a: TreeNode, b: TreeNode): Unit = {
var temp: Int = a.data;
a.data = b.data;
b.data = temp;
}
// Swap leaf node elements in pairwise manner
def swapLeafPair(node: TreeNode): Unit = {
if (node != null)
{
if (node.left == null && node.right == null)
{
if (this.prev == null)
{
// First pair node
this.prev = node;
}
else
{
this.swapValue(node, this.prev);
// Reset pair element
this.prev = null;
}
return;
}
// Recursively visiting left and right subtree
this.swapLeafPair(node.left);
this.swapLeafPair(node.right);
}
}
// Handles the request of swapping leaf nodes
def swapLeafNodes(): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
return;
}
this.prev = null;
this.swapLeafPair(this.root);
}
//Display Inorder view of binary tree
def inorder(node: TreeNode): Unit = {
if (node != null)
{
this.inorder(node.left);
//Print node value
print(" " + node.data);
this.inorder(node.right);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(10);
tree.root.left.right.left = new TreeNode(7);
tree.root.right.left = new TreeNode(6);
tree.root.right.left.right = new TreeNode(9);
tree.root.right.right = new TreeNode(4);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
print("\n After Swap Leaf nodes \n");
tree.inorder(tree.root);
}
}
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
/*
Swift 4 Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode? ;
var prev: TreeNode? ;
init()
{
self.root = nil;
self.prev = nil;
}
// Swap the value of given nodes values
func swapValue(_ a: TreeNode? , _ b : TreeNode? )
{
let temp: Int = a!.data;
a!.data = b!.data;
b!.data = temp;
}
// Swap leaf node elements in pairwise manner
func swapLeafPair(_ node: TreeNode? )
{
if (node != nil)
{
if (node!.left == nil && node!.right == nil)
{
if (self.prev == nil)
{
// First pair node
self.prev = node;
}
else
{
self.swapValue(node, self.prev);
// Reset pair element
self.prev = nil;
}
return;
}
// Recursively visiting left and right subtree
self.swapLeafPair(node!.left);
self.swapLeafPair(node!.right);
}
}
// Handles the request of swapping leaf nodes
func swapLeafNodes()
{
if (self.root == nil)
{
print("\n Empty Tree ");
return;
}
self.prev = nil;
self.swapLeafPair(self.root);
}
//Display Inorder view of binary tree
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
//Print node value
print(" ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(10);
tree.root!.left!.right!.left = TreeNode(7);
tree.root!.right!.left = TreeNode(6);
tree.root!.right!.left!.right = TreeNode(9);
tree.root!.right!.right = TreeNode(4);
tree.root!.right!.left!.left = TreeNode(5);
tree.root!.right!.right!.right = TreeNode(11);
tree.root!.right!.right!.right!.left = TreeNode(12);
tree.root!.right!.right!.right!.right = TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
print("\n After Swap Leaf nodes ");
tree.inorder(tree.root);
}
main();
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
/*
Kotlin Program
Pairwise swap leaf nodes in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode ? ;
var prev: TreeNode ? ;
constructor()
{
this.root = null;
this.prev = null;
}
// Swap the value of given nodes values
fun swapValue(a: TreeNode , b : TreeNode ): Unit
{
var temp: Int = a.data;
a.data = b.data;
b.data = temp;
}
// Swap leaf node elements in pairwise manner
fun swapLeafPair(node: TreeNode ? ): Unit
{
if (node != null)
{
if (node.left == null && node.right == null)
{
if (this.prev == null)
{
// First pair node
this.prev = node;
}
else
{
var temp: Int = node.data;
node.data = this.prev!!.data;
this.prev!!.data = temp;
// Reset pair element
this.prev = null;
}
return;
}
// Recursively visiting left and right subtree
this.swapLeafPair(node.left);
this.swapLeafPair(node.right);
}
}
// Handles the request of swapping leaf nodes
fun swapLeafNodes(): Unit
{
if (this.root == null)
{
print("\n Empty Tree \n");
return;
}
this.prev = null;
this.swapLeafPair(this.root);
}
//Display Inorder view of binary tree
fun inorder(node: TreeNode ? ): Unit
{
if (node != null)
{
this.inorder(node.left);
//Print node value
print(" " + node.data);
this.inorder(node.right);
}
}
}
fun main(args: Array < String > ): Unit
{
var tree: BinaryTree = BinaryTree();
/*
1
/ \
/ \
2 8
/ \ / \
3 10 6 4
/ / \ \
7 5 9 11
/ \
12 13
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(10);
tree.root?.left?.right?.left = TreeNode(7);
tree.root?.right?.left = TreeNode(6);
tree.root?.right?.left?.right = TreeNode(9);
tree.root?.right?.right = TreeNode(4);
tree.root?.right?.left?.left = TreeNode(5);
tree.root?.right?.right?.right = TreeNode(11);
tree.root?.right?.right?.right?.left = TreeNode(12);
tree.root?.right?.right?.right?.right = TreeNode(13);
tree.inorder(tree.root);
tree.swapLeafNodes();
/*
1
/ \
/ \
2 8
/ \ / \
7 10 6 4
/ / \ \
3 9 5 11
/ \
13 12
-----------------------
After swap leaf node pairs
-----------------------
*/
print("\n After Swap Leaf nodes \n");
tree.inorder(tree.root);
}
Output
3 2 7 10 1 5 6 9 8 4 12 11 13
After Swap Leaf nodes
7 2 3 10 1 9 6 5 8 4 13 11 12
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment