Code Implementation

# Definition for a Node.
# class Node:
#     def __init__(self, val, left, right, parent):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.parent = parent

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        if node.right:
            # Go to the leftmost node in the right subtree
            curr = node.right
            while curr.left:
                curr = curr.left
            return curr
        # Go up until we come from left
        curr = node
        while curr.parent and curr == curr.parent.right:
            curr = curr.parent
        return curr.parent
      

/*
Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if (node->right) {
            Node* curr = node->right;
            while (curr->left) {
                curr = curr->left;
            }
            return curr;
        }
        Node* curr = node;
        while (curr->parent && curr == curr->parent->right) {
            curr = curr->parent;
        }
        return curr->parent;
    }
};
      

/*
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node inorderSuccessor(Node node) {
        if (node.right != null) {
            Node curr = node.right;
            while (curr.left != null) {
                curr = curr.left;
            }
            return curr;
        }
        Node curr = node;
        while (curr.parent != null && curr == curr.parent.right) {
            curr = curr.parent;
        }
        return curr.parent;
    }
}
      

/**
 * // Definition for a Node.
 * function Node(val, left, right, parent) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *     this.parent = parent;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var inorderSuccessor = function(node) {
    if (node.right) {
        let curr = node.right;
        while (curr.left) {
            curr = curr.left;
        }
        return curr;
    }
    let curr = node;
    while (curr.parent && curr === curr.parent.right) {
        curr = curr.parent;
    }
    return curr.parent;
};
      

Problem Description

You are given a node node in a binary search tree (BST). Each node has a parent pointer in addition to its left and right children. Your task is to find the in-order successor of the given node in the BST.

• The in-order successor of a node is the node with the smallest key greater than the given node's value.
• You must return null if the given node has no in-order successor.
• It is guaranteed that the given node exists in the tree.
• Each node has a unique value.
• Do not reuse or modify elements in the tree.

Thought Process

To solve this problem, it's important to recall what an in-order traversal of a BST looks like: it visits nodes in ascending order. The in-order successor of a node is the next node visited after the current node during such a traversal.

The naive approach would be to perform a full in-order traversal of the tree, collect all nodes in a list, and then find the node following the given one. However, this would be inefficient and unnecessary, especially since each node has a parent pointer, allowing us to move upwards in the tree.

By leveraging the BST properties and the parent pointer, we can identify two main cases:

• If the node has a right child, its successor is the leftmost node in its right subtree.
• If it doesn't have a right child, we move up the tree using the parent pointer until we find a node that is a left child of its parent; then, its parent is the successor.

This approach is much more efficient and elegant than traversing the entire tree.

Solution Approach

• Case 1: Node has a right child
  • Go to the right child of the node.
  • From there, keep going to the left child until you can't go further.
  • The last node you reach is the in-order successor.
• Case 2: Node does not have a right child
  • Move up to the parent node repeatedly, as long as the current node is a right child of its parent.
  • Stop when the current node becomes a left child of its parent.
  • The parent at this point is the in-order successor. If you reach the root (parent is null), then there is no successor.

This method efficiently finds the successor in O(h) time, where h is the height of the tree, without needing extra space.

Example Walkthrough

Let's consider the following BST:

        5
       / \
      3   6
     / \
    2   4
   /
  1
  

Suppose node = 3. What is its in-order successor?

1. Does 3 have a right child? Yes, it has 4.
   • Go to 4. 4 has no left child, so 4 is the in-order successor of 3.
2. Now, suppose node = 4.
   • 4 has no right child.
   • Move up to its parent (3). 4 is the right child of 3, so move up again to 5.
   • 4 is in the left subtree of 5, so 5 is the successor of 4.
3. For node = 6:
   • 6 has no right child and is the right child of 5. Move up to 5. 6 is the right child of 5, and 5 has no parent. So, 6 has no in-order successor (returns null).

Time and Space Complexity

• Brute-force approach:
  • Time: O(N) to traverse the entire tree.
  • Space: O(N) to store the nodes in a list.
• Optimized approach (with parent pointer):
  • Time: O(h), where h is the height of the tree, since we may traverse up or down the tree at most h steps.
  • Space: O(1), as we only use a constant amount of extra memory.

The optimized approach is efficient both in time and space, especially for balanced BSTs where h = log N.

Summary

By leveraging the BST's properties and the presence of a parent pointer, we can efficiently find the in-order successor of a node without traversing the entire tree. The key insight is to distinguish between nodes with and without right children and to use upwards traversal only when necessary. This results in a clean, elegant, and optimal solution.