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 : 6
package 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 : 6

Time 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







© 2021, kalkicode.com, All rights reserved