Inorder successor of a node in binary tree
Given a binary tree which include node elements. Our goal is to find inorder successor of particular node. Which is exist in binary tree.
What is inorder successor
A next node which is part of inorder sequence is called inorder successor of previous node. Note that the last node of inorder sequence has no successor so it indicate NULL (None). For Example.
Binary Tree
-------------------------
1
/ \
2 5
/ \
7 3
------------------------
Inorder [7,2,3,1,5]
// input value indicates node which contains value
Input 7
Output 2 [Next node inorder sequence]
Input 5
Output NULL [No successor in last node]
Input 3
Output 1 We solve this problem using iterative and recursive manner. We given below solution is based on recursive approach.
/*
Java program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
// Display tree element inorder form
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Print node value
System.out.print(" " + node.data);
inorder(node.right);
}
}
public void findSuccessor(TreeNode node,
TreeNode lp, TreeNode rp, TreeNode n)
{
if (node != null && n != null)
{
// Recursively visiting left and right subtree
findSuccessor(node.left, lp, node, n);
findSuccessor(node.right, node, rp, n);
// Successor Condition
if (node.left == null && lp != null && lp == n)
{
System.out.print("\n Successor of node " +
n.data + " is : " + node.data);
}
else if (node.right == null && rp != null && node == n)
{
System.out.print("\n Successor of node " +
n.data + " is : " + rp.data);
}
else if (node.right == null && rp == null && node == n)
{
System.out.print("\n Successor of node " +
n.data + " is : None ");
}
}
}
// This method are handles the request
// of finding successor in given node
public void successor(TreeNode node)
{
if(node==null || this.root == null)
{
// Invalid node or empty tree
return;
}
this.findSuccessor(this.root, null, null, node);
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(6);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
// Display tree element
tree.inorder(tree.root);
// Get tree node
TreeNode node = tree.root.right.left;
tree.successor(node);
// Get new tree node
node = tree.root.left.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right.left;
tree.successor(node);
}
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6// C Program
// Inorder successor of a node in binary tree
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode * left;
struct TreeNode * right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode * root;
};
// Create new tree
struct BinaryTree * newTree()
{
// Create dynamic node
struct BinaryTree * tree =
(struct BinaryTree * ) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// return new tree
return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode * newNode(int data)
{
// Create dynamic node
struct TreeNode * node = (struct TreeNode * ) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates,
// segmentation fault or memory overflow problem
printf("Memory Overflow\n");
exit(0);
}
// return
return node;
}
// Display tree element inorder form
void inorder(struct TreeNode * node)
{
if (node != NULL)
{
inorder(node->left);
// Print node value
printf(" %d", node->data);
inorder(node->right);
}
}
void findSuccessor(struct TreeNode * node,
struct TreeNode * lp,
struct TreeNode * rp, struct TreeNode * n)
{
if (node != NULL && n != NULL)
{
findSuccessor(node->left, lp, node, n);
findSuccessor(node->right, node, rp, n);
// Successor Condition
if (node->left == NULL && lp != NULL && lp == n)
{
printf("\n Successor of node %d is : %d ", n->data, node->data);
}
else if (node->right == NULL && rp != NULL && node == n)
{
printf("\n Successor of node %d is : %d ", n->data, rp->data);
}
else if (node->right == NULL && rp == NULL && node == n)
{
printf("\n Successor of node %d is : NULL ", n->data);
}
}
}
// This method are handles the request
// of finding successor in given node
void successor(struct TreeNode * root,struct TreeNode *node)
{
if (node == NULL || root == NULL)
{
// Invalid node or empty tree
return;
}
findSuccessor(root, NULL, NULL, node);
}
int main()
{
struct BinaryTree * tree = newTree();
/*Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree->root = newNode(1);
tree->root->left = newNode(2);
tree->root->right = newNode(3);
tree->root->right->right = newNode(9);
tree->root->right->left = newNode(5);
tree->root->right->left->right = newNode(6);
tree->root->left->left = newNode(4);
tree->root->left->left->right = newNode(7);
tree->root->right->left->right->left = newNode(8);
// Display tree element
inorder(tree->root);
// Test
struct TreeNode * node = tree->root->right->left;
successor(tree->root, node);
node = tree->root->left->left->right;
successor(tree->root, node);
node = tree->root->right->right;
successor(tree->root, node);
node = tree->root->right->left->right;
successor(tree->root, node);
node = tree->root->right->left->right->left;
successor(tree->root, node);
return 0;
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : NULL
Successor of node 6 is : 3
Successor of node 8 is : 6package main
import "fmt"
/*
Go program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
// Display tree element inorder form
func(this BinaryTree) inorder(node * TreeNode) {
if node != nil {
this.inorder(node.left)
// Print node value
fmt.Print(" ", node.data)
this.inorder(node.right)
}
}
func(this BinaryTree) findSuccessor(node, lp, rp, n *TreeNode) {
if node != nil && n != nil {
// Recursively visiting left and right subtree
this.findSuccessor(node.left, lp, node, n)
this.findSuccessor(node.right, node, rp, n)
// Successor Condition
if node.left == nil && lp != nil && lp == n {
fmt.Print("\n Successor of node ", n.data, " is : ", node.data)
} else if node.right == nil && rp != nil && node == n {
fmt.Print("\n Successor of node ", n.data, " is : ", rp.data)
} else if node.right == nil && rp == nil && node == n {
fmt.Print("\n Successor of node ", n.data, " is : None ")
}
}
}
// This method are handles the request
// of finding successor in given node
func(this BinaryTree) successor(node * TreeNode) {
if node == nil || this.root == nil {
// Invalid node or empty tree
return
}
this.findSuccessor(this.root, nil, nil, node)
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(2)
tree.root.right = getTreeNode(3)
tree.root.right.right = getTreeNode(9)
tree.root.right.left = getTreeNode(5)
tree.root.right.left.right = getTreeNode(6)
tree.root.left.left = getTreeNode(4)
tree.root.left.left.right = getTreeNode(7)
tree.root.right.left.right.left = getTreeNode(8)
// Display tree element
tree.inorder(tree.root)
// Get tree node
var node * TreeNode = tree.root.right.left
tree.successor(node)
// Get new tree node
node = tree.root.left.left.right
tree.successor(node)
// Get new tree node
node = tree.root.right.right
tree.successor(node)
// Get new tree node
node = tree.root.right.left.right
tree.successor(node)
// Get new tree node
node = tree.root.right.left.right.left
tree.successor(node)
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Display tree element inorder form
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
// Print node value
cout << " " << node->data;
this->inorder(node->right);
}
}
void findSuccessor(TreeNode *node,
TreeNode *lp,
TreeNode *rp,
TreeNode *n)
{
if (node != NULL && n != NULL)
{
// Recursively visiting left and right subtree
this->findSuccessor(node->left, lp, node, n);
this->findSuccessor(node->right, node, rp, n);
// Successor Condition
if (node->left == NULL && lp != NULL && lp == n)
{
cout << "\n Successor of node "
<< n->data << " is : " << node->data;
}
else if (node->right == NULL && rp != NULL && node == n)
{
cout << "\n Successor of node "
<< n->data << " is : " << rp->data;
}
else if (node->right == NULL && rp == NULL && node == n)
{
cout << "\n Successor of node "
<< n->data << " is : None ";
}
}
}
// This method are handles the request
// of finding successor in given node
void successor(TreeNode *node)
{
if (node == NULL || this->root == NULL)
{
// Invalid node or empty tree
return;
}
this->findSuccessor(this->root, NULL, NULL, node);
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(2);
tree->root->right = new TreeNode(3);
tree->root->right->right = new TreeNode(9);
tree->root->right->left = new TreeNode(5);
tree->root->right->left->right = new TreeNode(6);
tree->root->left->left = new TreeNode(4);
tree->root->left->left->right = new TreeNode(7);
tree->root->right->left->right->left = new TreeNode(8);
// Display tree element
tree->inorder(tree->root);
// Get tree node
TreeNode *node = tree->root->right->left;
tree->successor(node);
// Get new tree node
node = tree->root->left->left->right;
tree->successor(node);
// Get new tree node
node = tree->root->right->right;
tree->successor(node);
// Get new tree node
node = tree->root->right->left->right;
tree->successor(node);
// Get new tree node
node = tree->root->right->left->right->left;
tree->successor(node);
return 0;
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6// Include namespace system
using System;
/*
Csharp program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
// Display tree element inorder form
public void inorder(TreeNode node)
{
if (node != null)
{
this.inorder(node.left);
// Print node value
Console.Write(" " + node.data);
this.inorder(node.right);
}
}
public void findSuccessor(TreeNode node,
TreeNode lp,
TreeNode rp,
TreeNode n)
{
if (node != null && n != null)
{
// Recursively visiting left and right subtree
this.findSuccessor(node.left, lp, node, n);
this.findSuccessor(node.right, node, rp, n);
// Successor Condition
if (node.left == null && lp != null && lp == n)
{
Console.Write("\n Successor of node " +
n.data + " is : " + node.data);
}
else if (node.right == null && rp != null && node == n)
{
Console.Write("\n Successor of node " +
n.data + " is : " + rp.data);
}
else if (node.right == null && rp == null && node == n)
{
Console.Write("\n Successor of node " +
n.data + " is : None ");
}
}
}
// This method are handles the request
// of finding successor in given node
public void successor(TreeNode node)
{
if (node == null || this.root == null)
{
// Invalid node or empty tree
return;
}
this.findSuccessor(this.root, null, null, node);
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(6);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
// Display tree element
tree.inorder(tree.root);
// Get tree node
TreeNode node = tree.root.right.left;
tree.successor(node);
// Get new tree node
node = tree.root.left.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right.left;
tree.successor(node);
}
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6<?php
/*
Php program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
// Display tree element inorder form
public function inorder($node)
{
if ($node != NULL)
{
$this->inorder($node->left);
// Print node value
print_r(" ".strval($node->data));
$this->inorder($node->right);
}
}
public function findSuccessor($node, $lp, $rp, $n)
{
if ($node != NULL && $n != NULL)
{
// Recursively visiting left and right subtree
$this->findSuccessor($node->left, $lp, $node, $n);
$this->findSuccessor($node->right, $node, $rp, $n);
// Successor Condition
if ($node->left == NULL && $lp != NULL && $lp == $n)
{
print_r("\n Successor of node ".strval($n->data).
" is : ".strval($node->data));
}
else if ($node->right == NULL && $rp != NULL && $node == $n)
{
print_r("\n Successor of node ".strval($n->data).
" is : ".strval($rp->data));
}
else if ($node->right == NULL && $rp == NULL && $node == $n)
{
print_r("\n Successor of node ".strval($n->data).
" is : None ");
}
}
}
// This method are handles the request
// of finding successor in given node
public function successor($node)
{
if ($node == NULL || $this->root == NULL)
{
// Invalid node or empty tree
return;
}
$this->findSuccessor($this->root, NULL, NULL, $node);
}
public static
function main($args)
{
$tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->right->right = new TreeNode(9);
$tree->root->right->left = new TreeNode(5);
$tree->root->right->left->right = new TreeNode(6);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->left->right = new TreeNode(7);
$tree->root->right->left->right->left = new TreeNode(8);
// Display tree element
$tree->inorder($tree->root);
// Get tree node
$node = $tree->root->right->left;
$tree->successor($node);
// Get new tree node
$node = $tree->root->left->left->right;
$tree->successor($node);
// Get new tree node
$node = $tree->root->right->right;
$tree->successor($node);
// Get new tree node
$node = $tree->root->right->left->right;
$tree->successor($node);
// Get new tree node
$node = $tree->root->right->left->right->left;
$tree->successor($node);
}
}
BinaryTree::main(array());Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6/*
Node JS program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Display tree element inorder form
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
// Print node value
process.stdout.write(" " + node.data);
this.inorder(node.right);
}
}
findSuccessor(node, lp, rp, n)
{
if (node != null && n != null)
{
// Recursively visiting left and right subtree
this.findSuccessor(node.left, lp, node, n);
this.findSuccessor(node.right, node, rp, n);
// Successor Condition
if (node.left == null && lp != null && lp == n)
{
process.stdout.write("\n Successor of node " +
n.data + " is : " + node.data);
}
else if (node.right == null && rp != null && node == n)
{
process.stdout.write("\n Successor of node " +
n.data + " is : " + rp.data);
}
else if (node.right == null && rp == null && node == n)
{
process.stdout.write("\n Successor of node " +
n.data + " is : None ");
}
}
}
// This method are handles the request
// of finding successor in given node
successor(node)
{
if (node == null || this.root == null)
{
// Invalid node or empty tree
return;
}
this.findSuccessor(this.root, null, null, node);
}
}
function main()
{
var tree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(6);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
// Display tree element
tree.inorder(tree.root);
// Get tree node
var node = tree.root.right.left;
tree.successor(node);
// Get new tree node
node = tree.root.left.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right.left;
tree.successor(node);
}
main();Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6# Python 3 program for
# Inorder successor of a node in binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
# Display tree element inorder form
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
# Print node value
print(" ", node.data, end = "")
self.inorder(node.right)
def findSuccessor(self, node, lp, rp, n) :
if (node != None and n != None) :
# Recursively visiting left and right subtree
self.findSuccessor(node.left, lp, node, n)
self.findSuccessor(node.right, node, rp, n)
# Successor Condition
if (node.left == None and lp != None and lp == n) :
print("\n Successor of node ",
n.data ," is : ", node.data, end = "",sep="")
elif (node.right == None and rp != None and node == n) :
print("\n Successor of node ",
n.data ," is : ", rp.data, end = "",sep="")
elif (node.right == None and rp == None and node == n) :
print("\n Successor of node ",
n.data ," is : None ", end = "",sep="")
# This method are handles the request
# of finding successor in given node
def successor(self, node) :
if (node == None or self.root == None) :
# Invalid node or empty tree
return
self.findSuccessor(self.root, None, None, node)
def main() :
tree = BinaryTree()
# Make A Binary Tree
# -----------------------
# 1
# / \
# 2 3
# / / \
# 4 5 9
# \ \
# 7 6
# /
# 8
# Add tree node
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(9)
tree.root.right.left = TreeNode(5)
tree.root.right.left.right = TreeNode(6)
tree.root.left.left = TreeNode(4)
tree.root.left.left.right = TreeNode(7)
tree.root.right.left.right.left = TreeNode(8)
# Display tree element
tree.inorder(tree.root)
# Get tree node
node = tree.root.right.left
tree.successor(node)
# Get new tree node
node = tree.root.left.left.right
tree.successor(node)
# Get new tree node
node = tree.root.right.right
tree.successor(node)
# Get new tree node
node = tree.root.right.left.right
tree.successor(node)
# Get new tree node
node = tree.root.right.left.right.left
tree.successor(node)
if __name__ == "__main__": main()Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6# Ruby program for
# Inorder successor of a node in binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Display tree element inorder form
def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print(" ", node.data)
self.inorder(node.right)
end
end
def findSuccessor(node, lp, rp, n)
if (node != nil && n != nil)
# Recursively visiting left and right subtree
self.findSuccessor(node.left, lp, node, n)
self.findSuccessor(node.right, node, rp, n)
# Successor Condition
if (node.left == nil && lp != nil && lp == n)
print("\n Successor of node ",
n.data ," is : ", node.data)
elsif (node.right == nil && rp != nil && node == n)
print("\n Successor of node ", n.data ," is : ", rp.data)
elsif (node.right == nil && rp == nil && node == n)
print("\n Successor of node ", n.data ," is : None ")
end
end
end
# This method are handles the request
# of finding successor in given node
def successor(node)
if (node == nil || self.root == nil)
# Invalid node or empty tree
return
end
self.findSuccessor(self.root, nil, nil, node)
end
end
def main()
tree = BinaryTree.new()
# Make A Binary Tree
# -----------------------
# 1
# / \
# 2 3
# / / \
# 4 5 9
# \ \
# 7 6
# /
# 8
# Add tree node
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.right.right = TreeNode.new(9)
tree.root.right.left = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(6)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.right = TreeNode.new(7)
tree.root.right.left.right.left = TreeNode.new(8)
# Display tree element
tree.inorder(tree.root)
# Get tree node
node = tree.root.right.left
tree.successor(node)
# Get new tree node
node = tree.root.left.left.right
tree.successor(node)
# Get new tree node
node = tree.root.right.right
tree.successor(node)
# Get new tree node
node = tree.root.right.left.right
tree.successor(node)
# Get new tree node
node = tree.root.right.left.right.left
tree.successor(node)
end
main()Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6/*
Scala program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Display tree element inorder form
def inorder(node: TreeNode): Unit = {
if (node != null)
{
inorder(node.left);
// Print node value
print(" " + node.data);
inorder(node.right);
}
}
def findSuccessor(node: TreeNode,
lp: TreeNode,
rp: TreeNode,
n: TreeNode): Unit = {
if (node != null && n != null)
{
// Recursively visiting left and right subtree
findSuccessor(node.left, lp, node, n);
findSuccessor(node.right, node, rp, n);
// Successor Condition
if (node.left == null && lp != null && lp == n)
{
print("\n Successor of node " +
n.data + " is : " + node.data);
}
else if (node.right == null && rp != null && node == n)
{
print("\n Successor of node " +
n.data + " is : " + rp.data);
}
else if (node.right == null && rp == null && node == n)
{
print("\n Successor of node " +
n.data + " is : None ");
}
}
}
// This method are handles the request
// of finding successor in given node
def successor(node: TreeNode): Unit = {
if (node == null || this.root == null)
{
// Invalid node or empty tree
return;
}
this.findSuccessor(this.root, null, null, node);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(9);
tree.root.right.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(6);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
// Display tree element
tree.inorder(tree.root);
// Get tree node
var node: TreeNode = tree.root.right.left;
tree.successor(node);
// Get new tree node
node = tree.root.left.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right;
tree.successor(node);
// Get new tree node
node = tree.root.right.left.right.left;
tree.successor(node);
}
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6/*
Swift 4 program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Display tree element inorder form
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
// Print node value
print(" ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
func findSuccessor(_ node: TreeNode? ,
_ lp : TreeNode? ,
_ rp : TreeNode? ,
_ n : TreeNode? )
{
if (node != nil && n != nil)
{
// Recursively visiting left and right subtree
self.findSuccessor(node!.left, lp, node, n);
self.findSuccessor(node!.right, node, rp, n);
// Successor Condition
if (node!.left == nil && lp != nil && lp === n)
{
print("\n Successor of node ",
n!.data ," is : ", node!.data, terminator: "");
}
else if (node!.right == nil && rp != nil && node === n)
{
print("\n Successor of node ",
n!.data ," is : ", rp!.data, terminator: "");
}
else if (node!.right == nil && rp == nil && node === n)
{
print("\n Successor of node ",
n!.data ," is : None ", terminator: "");
}
}
}
// This method are handles the request
// of finding successor in given node
func successor(_ node: TreeNode? )
{
if (node == nil || self.root == nil)
{
// Invalid node or empty tree
return;
}
self.findSuccessor(self.root, nil, nil, node);
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.right!.right = TreeNode(9);
tree.root!.right!.left = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(6);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.right = TreeNode(7);
tree.root!.right!.left!.right!.left = TreeNode(8);
// Display tree element
tree.inorder(tree.root);
// Get tree node
var node: TreeNode? = tree.root!.right!.left;
tree.successor(node);
// Get new tree node
node = tree.root!.left!.left!.right;
tree.successor(node);
// Get new tree node
node = tree.root!.right!.right;
tree.successor(node);
// Get new tree node
node = tree.root!.right!.left!.right;
tree.successor(node);
// Get new tree node
node = tree.root!.right!.left!.right!.left;
tree.successor(node);
}
main();Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6/*
Kotlin program for
Inorder successor of a node in binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Display tree element inorder form
fun inorder(node: TreeNode ? ): Unit
{
if (node != null)
{
this.inorder(node.left);
// Print node value
print(" " + node.data);
this.inorder(node.right);
}
}
fun findSuccessor(node: TreeNode ? , lp : TreeNode ? ,
rp : TreeNode ? , n : TreeNode ? ): Unit
{
if (node != null && n != null)
{
// Recursively visiting left and right subtree
this.findSuccessor(node.left, lp, node, n);
this.findSuccessor(node.right, node, rp, n);
// Successor Condition
if (node.left == null && lp != null && lp == n)
{
print("\n Successor of node " +
n.data + " is : " + node.data);
}
else if (node.right == null &&
rp != null && node == n)
{
print("\n Successor of node " +
n.data + " is : " + rp.data);
}
else if (node.right == null &&
rp == null && node == n)
{
print("\n Successor of node " + n.data + " is : None ");
}
}
}
// This method are handles the request
// of finding successor in given node
fun successor(node: TreeNode ? ): Unit
{
if (node == null || this.root == null)
{
// Invalid node or empty tree
return;
}
this.findSuccessor(this.root, null, null, node);
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 9
\ \
7 6
/
8
*/
// Add tree node
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(3);
tree.root?.right?.right = TreeNode(9);
tree.root?.right?.left = TreeNode(5);
tree.root?.right?.left?.right = TreeNode(6);
tree.root?.left?.left = TreeNode(4);
tree.root?.left?.left?.right = TreeNode(7);
tree.root?.right?.left?.right?.left = TreeNode(8);
// Display tree element
tree.inorder(tree.root);
// Get tree node
var node: TreeNode ? = tree.root?.right?.left;
tree.successor(node);
// Get new tree node
node = tree.root?.left?.left?.right;
tree.successor(node);
// Get new tree node
node = tree.root?.right?.right;
tree.successor(node);
// Get new tree node
node = tree.root?.right?.left?.right;
tree.successor(node);
// Get new tree node
node = tree.root?.right?.left?.right?.left;
tree.successor(node);
}Output
4 7 2 1 5 8 6 3 9
Successor of node 5 is : 8
Successor of node 7 is : 2
Successor of node 9 is : None
Successor of node 6 is : 3
Successor of node 8 is : 6Time complexity of above program is O(n). Think about how to solve this problem in iterative manner. And submit your solution in comment box.
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