## 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

## 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class BinaryNode { BinaryNode left; BinaryNode right; BinaryNode parent; Integer data; public BinaryNode(BinaryNode left, BinaryNode right, Integer data) { super(); this.left = left; this.right = right; this.data = data; } } |

## Source Code – Inorder Successor of node in Binary Tree

Here is the iterative method to return inorder successor.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public BinaryNode inOrderSuccessor(BinaryNode node) { if (node == null) return null; if (node.right != null) { node = node.right; while (node.left != null) node = node.left; return node; } BinaryNode p = node.parent; while (p != null && p.right == node) { node = p; p = p.parent; } return p; } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
private BinaryNode createTreeNew() { BinaryNode n14 = new BinaryNode(null, null, 14); BinaryNode n13 = new BinaryNode(null, n14, 13); BinaryNode n12 = new BinaryNode(null, null, 12); BinaryNode n11 = new BinaryNode(null, null, 11); BinaryNode n10 = new BinaryNode(n11, n12, 10); BinaryNode n09 = new BinaryNode(null, null, 9); BinaryNode n08 = new BinaryNode(null, null, 8); BinaryNode n07 = new BinaryNode(n13, null, 7); BinaryNode n06 = new BinaryNode(null, n10, 6); BinaryNode n05 = new BinaryNode(n08, n09, 5); BinaryNode n04 = new BinaryNode(null, null, 4); BinaryNode n03 = new BinaryNode(n06, n07, 3); BinaryNode n02 = new BinaryNode(n04, n05, 2); BinaryNode n01 = new BinaryNode(n02, n03, 1); n02.parent = n01; n03.parent = n01; n04.parent = n02; n05.parent = n02; n06.parent = n03; n07.parent = n03; n08.parent = n05; n09.parent = n05; n10.parent = n06; n11.parent = n10; n12.parent = n10; n13.parent = n07; n14.parent = n13; return n01; } |

## 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.