Inorder Successor of node in Binary Tree Using Parent Pointer

Introduction

This is the sixth article in the Tree Traversals – Online Classes.

This article presents ways to find out inorder successor of node in binary tree. Before we jump into the code it would be good to correctly define the meaning of the problem.

Definition – Inorder Successor of node in Binary Tree

If a node K is called the inorder successor of node N then K must be visited immediately after N in a inorder traversal of the tree.

Below is a more formal definition of Inorder Successor:

  • If the node has a right sub-tree, then inorder successor is the left most node of the right sub-tree.
  • If the node doesn’t have a right sub-tree, then it is the first ancestor (when we move up from node to root) whose left sub-tree contains this node.

Here is the tree as an example. The inorder traversal of the tree is mentioned in the image as well
Inorder Successor of node in Binary Tree

Iterative Approach

We realize that, somewhere we need to look at the ancestors of the node, this means that it would be slightly tough or a more time consuming operation if we do not have the pointers to the ancestors. Hence, we will define a Binary Node structure which has a pointer to its parent as well. Here is the structure defined below:

Source Code – Inorder Successor of node in Binary Tree

Here is the iterative method to return inorder successor.

Here is the utility method to create a Binary Tree with all nodes pointing to their respective parent.

Analysis

The algorithm runs through the height of the tree downwards if there is a right sub-tree present for this node. It runs through the height of the tree upwards if there is no right sub-tree.
Hence, the running time is always O(logN) where N is the number of nodes. If the tree is skewed at one side, it might change to O(N)

Space Complexity of the algorithm is O(1) as there is no extra space required. We just need a temp binary node.

Don’t forget to subscribe to TechieMe to get updates on latest posts.

  • random_blogger

    Hey Dharam,

    You are modifying the structure of BinaryNode here, which may not be acceptable.
    A better approach would be keeping a stack while traversing the node and cross checking till the current node is not the right child of element in stack.

    • True! Let me modify the heading, “Using Parent Pointer” 🙂 Thanks for the suggestion. I will add more code on github and provide a link for the one you described.