{x}
blog image

Inorder Successor in BST II

510. Inorder Successor in BST II

Problem Description

Given a node in a binary search tree (BST), find its in-order successor. The in-order successor is the node with the smallest key greater than the given node's key. You have direct access to the node but not the root of the tree. Each node has a reference to its parent.

Solution Approach: Case Discussion

The solution uses a case-by-case approach based on the structure of the BST:

Case 1: Node has a right subtree:

If the node has a right subtree, the in-order successor is the leftmost node in that right subtree. This is because the in-order traversal visits the left subtree, then the node, then the right subtree. The leftmost node in the right subtree is the next node visited in an in-order traversal.

Case 2: Node does not have a right subtree:

If the node doesn't have a right subtree, we need to traverse upwards. We move up to the parent node. If the current node is the right child of its parent, we continue moving up until we find a parent where the current node is the left child. That parent node is the in-order successor. If we reach the root and the node is still a right child, there's no in-order successor (return null).

Code Implementation (Python)

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""
 
class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node
        while node.parent and node.parent.right is node:
            node = node.parent
        return node.parent

Time and Space Complexity Analysis

  • Time Complexity: O(h), where h is the height of the BST. In the worst case (a skewed tree), this becomes O(n), where n is the number of nodes. This is because we might need to traverse up the entire height of the tree.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Implementation in Other Languages

The logic remains the same across different programming languages; only the syntax changes. Below are examples in Java, C++, Go, TypeScript, and Javascript:

(Java)

/*
// Definition for a Node.
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 = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }
        return node.parent;
    }
}

(C++)

/*
// 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 = node->right;
            while (node->left) {
                node = node->left;
            }
            return node;
        }
        while (node->parent && node->parent->right == node) {
            node = node->parent;
        }
        return node->parent;
    }
};

(Go)

/**
 * Definition for Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Parent *Node
 * }
 */
 
func inorderSuccessor(node *Node) *Node {
	if node.Right != nil {
		node = node.Right
		for node.Left != nil {
			node = node.Left
		}
		return node
	}
	for node.Parent != nil && node == node.Parent.Right {
		node = node.Parent
	}
	return node.Parent
}

(TypeScript)

/**
 * Definition for a binary tree node.
 * class Node {
 *     val: number
 *     left: Node | null
 *     right: Node | null
 *     parent: Node | null
 *     constructor(val?: number, left?: Node | null, right?: Node | null, parent?: Node | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.parent = (parent===undefined ? null : parent)
 *     }
 * }
 */
 
function inorderSuccessor(node: Node | null): Node | null {
    if (node?.right) {
        node = node.right;
        while (node.left) {
            node = node.left;
        }
        return node;
    }
    while (node?.parent && node === node.parent.right) {
        node = node.parent;
    }
    return node?.parent;
}

(Javascript)

/**
 * // Definition for a Node.
 * function Node(val) {
 *    this.val = val;
 *    this.left = null;
 *    this.right = null;
 *    this.parent = null;
 * };
 */
 
/**
 * @param {Node} node
 * @return {Node}
 */
var inorderSuccessor = function (node) {
    if (node.right) {
        node = node.right;
        while (node.left) {
            node = node.left;
        }
        return node;
    }
    while (node.parent && node === node.parent.right) {
        node = node.parent;
    }
    return node.parent;
};