Given a Binary Search Tree (BST) and a target node, find the inorder predecessor of the given node. The inorder predecessor of a node is the previous node in the in-order traversal of the BST. If no predecessor exists (i.e., the node is the first in in-order traversal), return null
or equivalent.
Find the Inorder Predecessor in a Binary Search Tree
Problem Statement
Examples
Solution
Algorithm Steps
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left, *right, *parent;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = node->right = node->parent = NULL;
return node;
}
TreeNode* findInorderPredecessor(TreeNode* node) {
if (node->left) {
TreeNode* pred = node->left;
while (pred->right) pred = pred->right;
return pred;
}
TreeNode* curr = node;
while (curr->parent && curr == curr->parent->left) {
curr = curr->parent;
}
return curr->parent;
}
int main() {
TreeNode* root = createNode(20);
root->left = createNode(10);
root->right = createNode(30);
root->left->parent = root;
root->right->parent = root;
root->left->right = createNode(15);
root->left->right->parent = root->left;
TreeNode* node = root->left->right;
TreeNode* pred = findInorderPredecessor(node);
if (pred)
printf("Inorder predecessor of %d is %d\n", node->val, pred->val);
else
printf("No inorder predecessor found\n");
return 0;
}
Comments
Loading comments...