Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation 
3.
Solution Approach
3.1.
Python Implementation
3.1.1.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Auxiliary space complexity 
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is Inorder Traversal of a Tree?
4.3.
What is an inorder predecessor in a given binary tree?
4.4.
What is an inorder successor in a given binary tree?
4.5.
What is Preorder traversal?
5.
Conclusion
Last Updated: Mar 27, 2024

Replace each node in a binary tree with the sum of its inorder predecessor and successor

Author Teesha Goyal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A binary tree is another type of tree data structure that contains a single root node and two disjoint subtrees called the left and the right subtree. The maximum degree of any node of a binary tree is 2. To learn more about binary trees, visit our site, Binary Tree | Learn & Practice from Coding Ninjas Studio

This article will discuss the problem of replacing each node in a binary tree with the sum of its inorder predecessor and successor.

Problem Statement

You are given a binary tree containing N nodes. Your task is to replace each node in the given binary tree with the sum of its inorder predecessor and successor. Take 0 as the inorder predecessor of the leftmost leaf and the inorder successor of the rightmost leaf.

Example

Input

Output

Explanation 

The Inorder traversal of the given tree is 2, 5, 6, 1, 4, 3, 7

For 1:

The inorder predecessor is 6, and the inorder successor is 4.

Hence the sum = 10.

 

For 5:

The inorder predecessor is 2, and the inorder successor is 6.

Hence the sum = 8.

 

For 3: 

The inorder predecessor is 4, and the inorder successor is 7.

Hence the sum = 11.

 

For 2:

Since 2 is the leftmost leaf, the predecessor is taken as 0, and the successor is 5.

Hence the sum = 5.
 

For 6:

The inorder predecessor is 5, and the inorder successor is 1.

Hence the sum = 6.
 

For 4:

The inorder predecessor is 1, and the inorder successor is 3.

Hence the sum = 4.

 

For 7:

The inorder predecessor is 3, and since it is the rightmost leaf, its inorder successor is taken to be 0.

Hence the sum = 3.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

The solution to the problem is pretty straightforward. We will use an array to store the inorder traversal of the tree. Add a preceding and a trailing zero to set the inorder predecessor of the leftmost leaf and the inorder successor of the rightmost leaf as zero. Traverse again in an inorder fashion. For each node i, in the traversal, replace the node’s value with the sum of its inorder predecessor and successor stored in the array created earlier. 
 

The algorithm of the solution is:

  • Take a binary tree you want to make the replacements on.
     
  • Display the preorder traversal of the given binary tree.
     
  • Create a temporary array that contains the inorder traversal of the given binary tree. This array will be used as a reference to get the inorder predecessor and successor of a node. Add a preceding and trailing zero in the temporary array.
     
  • Again traverse the given binary tree in an inorder manner and replace the value of node i with temp[i-1] + temp[i+1], where temp[i-1] is the inorder predecessor, and temp[i+1] is the inorder successor.
     
  • Display the preorder traversal of the obtained binary tree.

Python Implementation

'''A class to create the binary tree'''
class Node:
    '''Constructor of the class'''
    def __init__(self, data):
        self.data = data
        self.left = self.right = None


'''Function to store the Inorder Traveral of given binary tree in temp array'''
def InorderTraveral(root, temp):
    '''Base Case if tree is empty'''
    if (not root):
        return
   
    '''Traversing for left tree recursively'''
    InorderTraveral(root.left, temp)
   
    '''Storing the value of root node in temp'''
    temp.append(root.data)
   
    '''Traversing for right tree recursively'''
    InorderTraveral(root.right, temp)
   
   
'''Function that performs replacing nodes'''
def ReplacingNodes(root, temp, i):
   
    '''Base Case if tree is empty'''
    if (not root):
        return
   
    '''Traversing for left tree recursively'''
    ReplacingNodes(root.left, temp, i)
   
    '''Replacing the root node with the sum of its predecessor and successor'''
    root.data = temp[i[0]-1] + temp[i[0]+1]
    i[0] += 1
   
    '''Traversing for right tree recursively'''
    ReplacingNodes(root.right, temp, i)
   

'''Function that takes the root node and replaces node with the sum of its inorder predecessor and successor'''    
def ReplaceNodeWithSum(root):
   
    '''Base Case if tree is empty'''
    if (not root):
        return
   
    '''creating a temp array that stores the inorder traversal of the binary tree'''
    temp = []
   
    '''Storing 0 at start for the inorder predecessor of the leftmost leaf'''
    temp.append(0)
   
    InorderTraveral(root, temp)
   
    ''''Storing 0 at last for the Inorder successor of the rightmost leaf'''
    temp.append(0)
   
    i = [1]
    ReplacingNodes(root, temp, i)


'''To print the preorder of the tree before and after replacing the nodes with the sum'''
def DisplayPreorder(root):
   
    '''Base Case if the tree is empty.''
    if (not root):
        return
   
    print(root.data, end = " ")
   
    '''Recursively traverse the left subtree'''
    DisplayPreorder(root.left)
   
    '''Recursively traverse the left subtree'''
    DisplayPreorder(root.right)
   
   
''' Driver Function'''
def main():
   
    ''' Creating a binary tree'''
    root = Node(1)
    root.left = Node(5)
    root.right = Node(3)
    root.left.left = Node(2)
    root.left.right = Node(6)
    root.right.left = Node(4)
    root.right.right = Node(7)
   
    '''Display preorder traversal of the given tree'''
    print("Preorder Traversal of Given Binary Tree:")
    DisplayPreorder(root)
   
    ''' Calling the ReplaceNodeWithSum method on the given binary tree'''
    ReplaceNodeWithSum(root)
   
    '''Display preorder traversal after replacing the nodes with the sum'''
    print("\nPreorder Traversal After Replacements:")
    DisplayPreorder(root)
   
   
'''Executing Main'''
main()

Output

Preorder Traversal of Given Binary Tree:
1 5 2 6 3 4 7 
Preorder Traversal After Replacements:
10 8 5 6 11 4 3

Complexities

Time Complexity

The time complexity of the given solution is O(N), where N is the number of nodes in the given binary tree.  

Reason: We are traversing the complete binary tree, which means we look at each node once. Hence, the complexity of O(N).

Auxiliary space complexity 

The Auxiliary space complexity of the given solution is O(N), where N is the number of nodes in the given binary tree. 

Reason: We are creating a temp array to store the inorder traversal of the given binary tree. The size of the temp array is N+2 (+2 for preceding and trailing 0). Hence, the complexity of O(N).

Frequently Asked Questions

What is a Binary Tree?

A binary tree is another type of tree data structure that contains a single root node and two disjoint subtrees called the left and the right subtree. 

What is Inorder Traversal of a Tree?

Inorder Traversal is a Tree traversal algorithm where we follow the LNR rule that first traverses the left subtree, then looks at the root node, and moves on to traverse the right subtree.

What is an inorder predecessor in a given binary tree?

The inorder predecessor is the node that comes just before the given node in the inorder traversal. It is the rightmost leaf of the left subtree of the given node.

What is an inorder successor in a given binary tree?

The inorder successor is the node that comes just after the given node in the inorder traversal. It is the leftmost leaf of the right subtree of the given node.

What is Preorder traversal?

Preorder traversal is a tree traversal algorithm that works on the NLR principle. First, traverse the given node, then traverse the left subtree, followed by the traversal of the right subtree.

Conclusion

In this article, we discussed the problem of replacing each node in a binary tree with the sum of the node’s inorder predecessor and successor. We discussed the implementation and complexity of the solution to the problem.

I hope you would have gained a better understanding of these topics now!

 

Recommended problems -

 

Are you planning to ace the interviews of reputed product-based companies like AmazonGoogleMicrosoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Construct a Binary Tree from the given Parent Array Representation
Next article
Replace Every Node of an N-ary Tree with the Sum of all its Subtrees
Live masterclass