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:
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 Predecessor of node in Binary Tree

Here is the iterative method to return inorder predecessor.
public BinaryNode inOrderPredecessor(BinaryNode node) {
    if (node == null)
        return null;

    if (node.left != null) {
        node = node.left;
        while (node.right != null)
            node = node.right;
        return node;
    }

    BinaryNode p = node.parent;

    while (p != null && p.left == 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.
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 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.