Inorder Predecessor of node in Binary Tree Using Parent Pointer

Introduction

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

This article presents ways to find out inorder predecessor of node in binary tree. As we have already read about the Inorder Successor it wont take much effort to understand the predecessor.

Definition – Inorder Predecessor of node in Binary Tree

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

Below is a more formal definition of Inorder Predecessor:

  • If the node has a left sub-tree, then inorder predecessor is the right most node of the left sub-tree.
  • If the node doesn’t have a left sub-tree, then it is the first ancestor (when we move up from node to root) whose right 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 Predecessor 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 Predecessor of node in Binary Tree

Here is the iterative method to return inorder predecessor.

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 left sub-tree present for this node. It runs through the height of the tree upwards if there is no left 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.