Skip to main content

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




Comment

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