Replace each node in binary tree with the sum of its inorder predecessor and successor
Here given code implementation process.
/*
C Program
Replace each node in binary tree with the sum of its inorder predecessor and successor
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return new node
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Display pre order elements
void preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
//replace each node value with preceding and successor
void replace(struct Node *node, struct Node *left_node, struct Node *right_node, int left_data, int right_data)
{
if (node == NULL)
{
return;
}
int value = node->data;
// Set the current node's value to zero data
node->data = 0;
// Recursively visits to left and right subtree
replace(node->left, left_node, node, left_data, value);
replace(node->right, node, right_node, value, right_data);
if (node->left == NULL && left_node != NULL)
{
//When the node left subtree is null. And the node exists inorder predecessor
/*
Example
x
\
y
/
node
/
NULL
node inorder predecessor is [x] in this example
*/
node->data += left_data;
}
if (node->right == NULL && right_node != NULL)
{
//When the node right subtree is null. And the node exists inorder successor
/*
Simple Example
x
/
y
\
node
\
NULL
node inorder successor is [x] in this example
*/
node->data += right_data;
}
if (left_node != NULL && node->left == NULL)
{
// When inorder predecessor not NULL and current node left is NULL
/*
Simple Example
x
/
/
left_node // Change this value
\
\
node
/
/
NULL
*/
left_node->data += value;
}
if (right_node != NULL && node->right == NULL)
{
// When inorder successor not NULL and current node right is NULL
/*
Simple Example
x
\
\
right_node // Change this value
/
/
node
\
\
NULL
*/
right_node->data += value;
}
}
void transform(struct Node *root)
{
if (root == NULL)
{
printf("\n Empty Tree \n");
}
else
{
//Before replace
printf("\n Tree Nodes \n");
preorder(root);
replace(root, NULL, NULL, 0, 0);
//After replace
printf("\n Tree Nodes \n");
preorder(root);
}
}
int main()
{
struct Node *root = NULL;
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
-----------------
Construct binary tree
*/
root = get_node(8);
root->left = get_node(5);
root->left->right = get_node(3);
root->left->right->right = get_node(9);
root->left->right->right->left = get_node(15);
root->left->left = get_node(1);
root->left->left->left = get_node(6);
root->right = get_node(10);
root->right->left = get_node(11);
root->right->left->right = get_node(4);
root->right->left->right->right = get_node(13);
root->right->right = get_node(2);
root->right->right->right = get_node(12);
root->right->right->right->right = get_node(17);
transform(root);
return 0;
}Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12/*
Java Program
Replace each node in binary tree with the sum of its inorder predecessor and successor
*/
// Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//Define Binary Tree
public class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set root of tree
this.root = null;
}
//Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
//replace each node value with preceding and successor
public void replace(Node node, Node left_node, Node right_node, int left_data, int right_data)
{
if (node == null)
{
return;
}
int value = node.data;
// Set the current node's value to zero data
node.data = 0;
// Recursively visits to left and right subtree
replace(node.left, left_node, node, left_data, value);
replace(node.right, node, right_node, value, right_data);
if (node.left == null && left_node != null)
{
//When the node left subtree is null. And the node exists inorder predecessor
/*
Example
x
\
y
/
node
/
NULL
node inorder predecessor is [x] in this example
*/
node.data += left_data;
}
if (node.right == null && right_node != null)
{
//When the node right subtree is null. And the node exists inorder successor
/*
Simple Example
x
/
y
\
node
\
NULL
node inorder successor is [x] in this example
*/
node.data += right_data;
}
if (left_node != null && node.left == null)
{
// When inorder predecessor not NULL and current node left is NULL
/*
Simple Example
x
/
/
left_node // Change this value
\
\
node
/
/
NULL
*/
left_node.data += value;
}
if (right_node != null && node.right == null)
{
// When inorder successor not NULL and current node right is NULL
/*
Simple Example
x
\
\
right_node // Change this value
/
/
node
\
\
NULL
*/
right_node.data += value;
}
}
public void transform()
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
}
else
{
//Before replace
System.out.print("\n Tree Nodes \n");
preorder(root);
replace(this.root, null, null, 0, 0);
//After replace
System.out.print("\n Tree Nodes \n");
preorder(root);
}
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree = new BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
-----------------
Construct binary tree
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(6);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.left.right.right = new Node(13);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.root.right.right.right.right = new Node(17);
tree.transform();
}
}Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Replace each node in binary tree with the sum of its inorder predecessor and successor
// Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Define Binary Tree
class BinaryTree
{
public: Node *root;
BinaryTree()
{
// Set root of tree
this->root = NULL;
}
// Display pre order elements
void preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
// replace each node value with preceding and successor
void replace(Node *node, Node *left_node, Node *right_node, int left_data, int right_data)
{
if (node == NULL)
{
return;
}
int value = node->data;
// Set the current node's value to zero data
node->data = 0;
// Recursively visits to left and right subtree
this->replace(node->left, left_node, node, left_data, value);
this->replace(node->right, node, right_node, value, right_data);
if (node->left == NULL && left_node != NULL)
{
// When the node left subtree is null. And the node exists inorder predecessor
//
// Example
//
// x
// \
// y
// /
// node
// /
// NULL
// node inorder predecessor is [x] in this example
//
node->data += left_data;
}
if (node->right == NULL && right_node != NULL)
{
// When the node right subtree is null. And the node exists inorder successor
//
// Simple Example
//
// x
// /
// y
// \
// node
// \
// NULL
// node inorder successor is [x] in this example
//
node->data += right_data;
}
if (left_node != NULL && node->left == NULL)
{
// When inorder predecessor not NULL and current node left is NULL
//
// Simple Example
//
// x
// /
// /
// left_node // Change this value
// \
// \
// node
// /
// /
// NULL
//
//
left_node->data += value;
}
if (right_node != NULL && node->right == NULL)
{
// When inorder successor not NULL and current node right is NULL
//
// Simple Example
//
// x
// \
// \
// right_node // Change this value
// /
// /
// node
// \
// \
// NULL
//
right_node->data += value;
}
}
void transform()
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
}
else
{
// Before replace
cout << "\n Tree Nodes \n";
this->preorder(this->root);
this->replace(this->root, NULL, NULL, 0, 0);
// After replace
cout << "\n Tree Nodes \n";
this->preorder(this->root);
}
}
};
int main()
{
// Create tree object
BinaryTree tree = BinaryTree();
// 8
// / \
// / \
// / \
// 5 10
// / \ / \
// 1 3 11 2
// / \ \ \
// 6 9 4 12
// / \ \
// 15 13 17
// -----------------
// Construct binary tree
tree.root = new Node(8);
tree.root->left = new Node(5);
tree.root->left->right = new Node(3);
tree.root->left->right->right = new Node(9);
tree.root->left->right->right->left = new Node(15);
tree.root->left->left = new Node(1);
tree.root->left->left->left = new Node(6);
tree.root->right = new Node(10);
tree.root->right->left = new Node(11);
tree.root->right->left->right = new Node(4);
tree.root->right->left->right->right = new Node(13);
tree.root->right->right = new Node(2);
tree.root->right->right->right = new Node(12);
tree.root->right->right->right->right = new Node(17);
tree.transform();
return 0;
}Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12// Include namespace system
using System;
// C# Program
// Replace each node in binary tree with the sum of its inorder predecessor and successor
// Binary Tree node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
public class BinaryTree
{
public Node root;
public BinaryTree()
{
// Set root of tree
this.root = null;
}
// Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// replace each node value with preceding and successor
public void replace(Node node, Node left_node, Node right_node, int left_data, int right_data)
{
if (node == null)
{
return;
}
int value = node.data;
// Set the current node's value to zero data
node.data = 0;
// Recursively visits to left and right subtree
replace(node.left, left_node, node, left_data, value);
replace(node.right, node, right_node, value, right_data);
if (node.left == null && left_node != null)
{
// When the node left subtree is null. And the node exists inorder predecessor
//
// Example
//
// x
// \
// y
// /
// node
// /
// NULL
// node inorder predecessor is [x] in this example
//
node.data += left_data;
}
if (node.right == null && right_node != null)
{
// When the node right subtree is null. And the node exists inorder successor
//
// Simple Example
//
// x
// /
// y
// \
// node
// \
// NULL
// node inorder successor is [x] in this example
//
node.data += right_data;
}
if (left_node != null && node.left == null)
{
// When inorder predecessor not NULL and current node left is NULL
//
// Simple Example
//
// x
// /
// /
// left_node // Change this value
// \
// \
// node
// /
// /
// NULL
//
//
left_node.data += value;
}
if (right_node != null && node.right == null)
{
// When inorder successor not NULL and current node right is NULL
//
// Simple Example
//
// x
// \
// \
// right_node // Change this value
// /
// /
// node
// \
// \
// NULL
//
right_node.data += value;
}
}
public void transform()
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
}
else
{
// Before replace
Console.Write("\n Tree Nodes \n");
preorder(root);
replace(this.root, null, null, 0, 0);
// After replace
Console.Write("\n Tree Nodes \n");
preorder(root);
}
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree = new BinaryTree();
//
// 8
// / \
// / \
// / \
// 5 10
// / \ / \
// 1 3 11 2
// / \ \ \
// 6 9 4 12
// / \ \
// 15 13 17
// -----------------
// Construct binary tree
//
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(6);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.left.right.right = new Node(13);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.root.right.right.right.right = new Node(17);
tree.transform();
}
}Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12<?php
// Php Program
// Replace each node in binary tree with the sum of its inorder predecessor and successor
// Binary Tree node
class Node
{
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;
function __construct()
{
// Set root of tree
$this->root = null;
}
// Display pre order elements
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// replace each node value with preceding and successor
public function replace($node, $left_node, $right_node, $left_data, $right_data)
{
if ($node == null)
{
return;
}
$value = $node->data;
// Set the current node's value to zero data
$node->data = 0;
// Recursively visits to left and right subtree
$this->replace($node->left, $left_node, $node, $left_data, $value);
$this->replace($node->right, $node, $right_node, $value, $right_data);
if ($node->left == null && $left_node != null)
{
// When the node left subtree is null. And the node exists inorder predecessor
//
// Example
//
// x
// \
// y
// /
// node
// /
// NULL
// node inorder predecessor is [x] in this example
//
$node->data += $left_data;
}
if ($node->right == null && $right_node != null)
{
// When the node right subtree is null. And the node exists inorder successor
//
// Simple Example
//
// x
// /
// y
// \
// node
// \
// NULL
// node inorder successor is [x] in this example
//
$node->data += $right_data;
}
if ($left_node != null && $node->left == null)
{
// When inorder predecessor not NULL and current node left is NULL
//
// Simple Example
//
// x
// /
// /
// left_node // Change this value
// \
// \
// node
// /
// /
// NULL
//
//
$left_node->data += $value;
}
if ($right_node != null && $node->right == null)
{
// When inorder successor not NULL and current node right is NULL
//
// Simple Example
//
// x
// \
// \
// right_node // Change this value
// /
// /
// node
// \
// \
// NULL
//
$right_node->data += $value;
}
}
public function transform()
{
if ($this->root == null)
{
echo "\n Empty Tree \n";
}
else
{
// Before replace
echo "\n Tree Nodes \n";
$this->preorder($this->root);
$this->replace($this->root, null, null, 0, 0);
// After replace
echo "\n Tree Nodes \n";
$this->preorder($this->root);
}
}
}
function main()
{
// Create tree object
$tree = new BinaryTree();
//
// 8
// / \
// / \
// / \
// 5 10
// / \ / \
// 1 3 11 2
// / \ \ \
// 6 9 4 12
// / \ \
// 15 13 17
// -----------------
// Construct binary tree
//
$tree->root = new Node(8);
$tree->root->left = new Node(5);
$tree->root->left->right = new Node(3);
$tree->root->left->right->right = new Node(9);
$tree->root->left->right->right->left = new Node(15);
$tree->root->left->left = new Node(1);
$tree->root->left->left->left = new Node(6);
$tree->root->right = new Node(10);
$tree->root->right->left = new Node(11);
$tree->root->right->left->right = new Node(4);
$tree->root->right->left->right->right = new Node(13);
$tree->root->right->right = new Node(2);
$tree->root->right->right->right = new Node(12);
$tree->root->right->right->right->right = new Node(17);
$tree->transform();
}
main();Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12//
// Node Js Program
// Replace each node in binary tree with the sum of its inorder predecessor and successor
// Binary Tree node
class Node
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
}
// Display pre order elements
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// replace each node value with preceding and successor
replace(node, left_node, right_node, left_data, right_data)
{
if (node == null)
{
return;
}
var value = node.data;
// Set the current node's value to zero data
node.data = 0;
// Recursively visits to left and right subtree
this.replace(node.left, left_node, node, left_data, value);
this.replace(node.right, node, right_node, value, right_data);
if (node.left == null && left_node != null)
{
// When the node left subtree is null. And the node exists inorder predecessor
//
// Example
//
// x
// \
// y
// /
// node
// /
// NULL
// node inorder predecessor is [x] in this example
//
node.data += left_data;
}
if (node.right == null && right_node != null)
{
// When the node right subtree is null. And the node exists inorder successor
//
// Simple Example
//
// x
// /
// y
// \
// node
// \
// NULL
// node inorder successor is [x] in this example
//
node.data += right_data;
}
if (left_node != null && node.left == null)
{
// When inorder predecessor not NULL and current node left is NULL
//
// Simple Example
//
// x
// /
// /
// left_node // Change this value
// \
// \
// node
// /
// /
// NULL
//
//
left_node.data += value;
}
if (right_node != null && node.right == null)
{
// When inorder successor not NULL and current node right is NULL
//
// Simple Example
//
// x
// \
// \
// right_node // Change this value
// /
// /
// node
// \
// \
// NULL
//
right_node.data += value;
}
}
transform()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
}
else
{
// Before replace
process.stdout.write("\n Tree Nodes \n");
this.preorder(this.root);
this.replace(this.root, null, null, 0, 0);
// After replace
process.stdout.write("\n Tree Nodes \n");
this.preorder(this.root);
}
}
}
function main()
{
// Create tree object
var tree = new BinaryTree();
//
// 8
// / \
// / \
// / \
// 5 10
// / \ / \
// 1 3 11 2
// / \ \ \
// 6 9 4 12
// / \ \
// 15 13 17
// -----------------
// Construct binary tree
//
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(6);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.left.right.right = new Node(13);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.root.right.right.right.right = new Node(17);
tree.transform();
}
main();Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12# Python 3 Program
# Replace each node in binary tree with the sum of its inorder predecessor and successor
# Binary Tree node
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
# Set root of tree
self.root = None
# Display pre order elements
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
# replace each node value with preceding and successor
def replace(self, node, left_node, right_node, left_data, right_data) :
if (node == None) :
return
value = node.data
# Set the current node's value to zero data
node.data = 0
# Recursively visits to left and right subtree
self.replace(node.left, left_node, node, left_data, value)
self.replace(node.right, node, right_node, value, right_data)
if (node.left == None and left_node != None) :
# When the node left subtree is null. And the node exists inorder predecessor
#
# Example
#
# x
# \
# y
# /
# node
# /
# NULL
# node inorder predecessor is [x] in this example
#
node.data += left_data
if (node.right == None and right_node != None) :
# When the node right subtree is null. And the node exists inorder successor
#
# Simple Example
#
# x
# /
# y
# \
# node
# \
# NULL
# node inorder successor is [x] in this example
#
node.data += right_data
if (left_node != None and node.left == None) :
# When inorder predecessor not NULL and current node left is NULL
#
# Simple Example
#
# x
# /
# /
# left_node // Change this value
# \
# \
# node
# /
# /
# NULL
#
#
left_node.data += value
if (right_node != None and node.right == None) :
# When inorder successor not NULL and current node right is NULL
#
# Simple Example
#
# x
# \
# \
# right_node // Change this value
# /
# /
# node
# \
# \
# NULL
#
right_node.data += value
def transform(self) :
if (self.root == None) :
print("\n Empty Tree \n", end = "")
else :
# Before replace
print("\n Tree Nodes \n", end = "")
self.preorder(self.root)
self.replace(self.root, None, None, 0, 0)
# After replace
print("\n Tree Nodes \n", end = "")
self.preorder(self.root)
def main() :
# Create tree object
tree = BinaryTree()
#
# 8
# / \
# / \
# / \
# 5 10
# / \ / \
# 1 3 11 2
# / \ \ \
# 6 9 4 12
# / \ \
# 15 13 17
# -----------------
# Construct binary tree
#
tree.root = Node(8)
tree.root.left = Node(5)
tree.root.left.right = Node(3)
tree.root.left.right.right = Node(9)
tree.root.left.right.right.left = Node(15)
tree.root.left.left = Node(1)
tree.root.left.left.left = Node(6)
tree.root.right = Node(10)
tree.root.right.left = Node(11)
tree.root.right.left.right = Node(4)
tree.root.right.left.right.right = Node(13)
tree.root.right.right = Node(2)
tree.root.right.right.right = Node(12)
tree.root.right.right.right.right = Node(17)
tree.transform()
if __name__ == "__main__": main()Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12# Ruby Program
# Replace each node in binary tree with the sum of its inorder predecessor and successor
# Binary Tree node
class Node
# Define the accessor and reader of class Node
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
attr_accessor :root
def initialize()
# Set root of tree
self.root = nil
end
# Display pre order elements
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
# replace each node value with preceding and successor
def replace(node, left_node, right_node, left_data, right_data)
if (node == nil)
return
end
value = node.data
# Set the current node's value to zero data
node.data = 0
# Recursively visits to left and right subtree
self.replace(node.left, left_node, node, left_data, value)
self.replace(node.right, node, right_node, value, right_data)
if (node.left == nil && left_node != nil)
# When the node left subtree is null. And the node exists inorder predecessor
#
# Example
#
# x
# \
# y
# /
# node
# /
# NULL
# node inorder predecessor is [x] in this example
#
node.data += left_data
end
if (node.right == nil && right_node != nil)
# When the node right subtree is null. And the node exists inorder successor
#
# Simple Example
#
# x
# /
# y
# \
# node
# \
# NULL
# node inorder successor is [x] in this example
#
node.data += right_data
end
if (left_node != nil && node.left == nil)
# When inorder predecessor not NULL and current node left is NULL
#
# Simple Example
#
# x
# /
# /
# left_node // Change this value
# \
# \
# node
# /
# /
# NULL
#
#
left_node.data += value
end
if (right_node != nil && node.right == nil)
# When inorder successor not NULL and current node right is NULL
#
# Simple Example
#
# x
# \
# \
# right_node // Change this value
# /
# /
# node
# \
# \
# NULL
#
right_node.data += value
end
end
def transform()
if (self.root == nil)
print("\n Empty Tree \n")
else
# Before replace
print("\n Tree Nodes \n")
self.preorder(root)
self.replace(self.root, nil, nil, 0, 0)
# After replace
print("\n Tree Nodes \n")
self.preorder(root)
end
end
end
def main()
# Create tree object
tree = BinaryTree.new()
#
# 8
# / \
# / \
# / \
# 5 10
# / \ / \
# 1 3 11 2
# / \ \ \
# 6 9 4 12
# / \ \
# 15 13 17
# -----------------
# Construct binary tree
#
tree.root = Node.new(8)
tree.root.left = Node.new(5)
tree.root.left.right = Node.new(3)
tree.root.left.right.right = Node.new(9)
tree.root.left.right.right.left = Node.new(15)
tree.root.left.left = Node.new(1)
tree.root.left.left.left = Node.new(6)
tree.root.right = Node.new(10)
tree.root.right.left = Node.new(11)
tree.root.right.left.right = Node.new(4)
tree.root.right.left.right.right = Node.new(13)
tree.root.right.right = Node.new(2)
tree.root.right.right.right = Node.new(12)
tree.root.right.right.right.right = Node.new(17)
tree.transform()
end
main()Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12// Scala Program
// Replace each node in binary tree with the sum of its inorder predecessor and successor
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Define Binary Tree
class BinaryTree(var root: Node)
{
def this()
{
this(null);
}
// Display pre order elements
def preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// replace each node value with preceding and successor
def replace(node: Node, left_node: Node, right_node: Node, left_data: Int, right_data: Int): Unit = {
if (node == null)
{
return;
}
var value: Int = node.data;
// Set the current node's value to zero data
node.data = 0;
// Recursively visits to left and right subtree
replace(node.left, left_node, node, left_data, value);
replace(node.right, node, right_node, value, right_data);
if (node.left == null && left_node != null)
{
// When the node left subtree is null. And the node exists inorder predecessor
//
// Example
//
// x
// \
// y
// /
// node
// /
// NULL
// node inorder predecessor is [x] in this example
//
node.data += left_data;
}
if (node.right == null && right_node != null)
{
// When the node right subtree is null. And the node exists inorder successor
//
// Simple Example
//
// x
// /
// y
// \
// node
// \
// NULL
// node inorder successor is [x] in this example
//
node.data += right_data;
}
if (left_node != null && node.left == null)
{
// When inorder predecessor not NULL and current node left is NULL
//
// Simple Example
//
// x
// /
// /
// left_node // Change this value
// \
// \
// node
// /
// /
// NULL
//
//
left_node.data += value;
}
if (right_node != null && node.right == null)
{
// When inorder successor not NULL and current node right is NULL
//
// Simple Example
//
// x
// \
// \
// right_node // Change this value
// /
// /
// node
// \
// \
// NULL
//
right_node.data += value;
}
}
def transform(): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
}
else
{
// Before replace
print("\n Tree Nodes \n");
preorder(root);
replace(this.root, null, null, 0, 0);
// After replace
print("\n Tree Nodes \n");
preorder(root);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree: BinaryTree = new BinaryTree();
//
// 8
// / \
// / \
// / \
// 5 10
// / \ / \
// 1 3 11 2
// / \ \ \
// 6 9 4 12
// / \ \
// 15 13 17
// -----------------
// Construct binary tree
//
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(6);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.left.right.right = new Node(13);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.root.right.right.right.right = new Node(17);
tree.transform();
}
}Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 12// Swift 4 Program
// Replace each node in binary tree with the sum of its inorder predecessor and successor
// Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Define Binary Tree
class BinaryTree
{
var root: Node? ;
init()
{
// Set root of tree
self.root = nil;
}
// Display pre order elements
func preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// replace each node value with preceding and successor
func replace(_ node: Node? , _ left_node : Node? , _ right_node : Node? , _ left_data : Int, _ right_data: Int)
{
if (node == nil)
{
return;
}
let value: Int = node!.data;
// Set the current node"s value to zero data
node!.data = 0;
// Recursively visits to left and right subtree
self.replace(node!.left, left_node, node, left_data, value);
self.replace(node!.right, node, right_node, value, right_data);
if (node!.left == nil && left_node != nil)
{
// When the node left subtree is null. And the node exists inorder predecessor
//
// Example
//
// x
// \
// y
// /
// node
// /
// NULL
// node inorder predecessor is [x] in this example
//
node!.data += left_data;
}
if (node!.right == nil && right_node != nil)
{
// When the node right subtree is null. And the node exists inorder successor
//
// Simple Example
//
// x
// /
// y
// \
// node
// \
// NULL
// node inorder successor is [x] in this example
//
node!.data += right_data;
}
if (left_node != nil && node!.left == nil)
{
// When inorder predecessor not NULL and current node left is NULL
//
// Simple Example
//
// x
// /
// /
// left_node // Change this value
// \
// \
// node
// /
// /
// NULL
//
//
left_node!.data += value;
}
if (right_node != nil && node!.right == nil)
{
// When inorder successor not NULL and current node right is NULL
//
// Simple Example
//
// x
// \
// \
// right_node // Change this value
// /
// /
// node
// \
// \
// NULL
//
right_node!.data += value;
}
}
func transform()
{
if (self.root == nil)
{
print("\n Empty Tree \n", terminator: "");
}
else
{
// Before replace
print("\n Tree Nodes \n", terminator: "");
self.preorder(self.root);
self.replace(self.root, nil, nil, 0, 0);
// After replace
print("\n Tree Nodes \n", terminator: "");
self.preorder(self.root);
}
}
}
func main()
{
// Create tree object
let tree: BinaryTree = BinaryTree();
//
// 8
// / \
// / \
// / \
// 5 10
// / \ / \
// 1 3 11 2
// / \ \ \
// 6 9 4 12
// / \ \
// 15 13 17
// -----------------
// Construct binary tree
//
tree.root = Node(8);
tree.root!.left = Node(5);
tree.root!.left!.right = Node(3);
tree.root!.left!.right!.right = Node(9);
tree.root!.left!.right!.right!.left = Node(15);
tree.root!.left!.left = Node(1);
tree.root!.left!.left!.left = Node(6);
tree.root!.right = Node(10);
tree.root!.right!.left = Node(11);
tree.root!.right!.left!.right = Node(4);
tree.root!.right!.left!.right!.right = Node(13);
tree.root!.right!.right = Node(2);
tree.root!.right!.right!.right = Node(12);
tree.root!.right!.right!.right!.right = Node(17);
tree.transform();
}
main();Output
Tree Nodes
8 5 1 6 3 9 15 10 11 4 13 2 12 17
Tree Nodes
20 4 11 1 20 23 12 15 12 24 14 22 19 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