inOrder Predecessor given node

I have a Binary Tree and I want to find the inOrderPredecessor given the node. I'm aware it would be easier using the root, but I'm testing out other methods.
I have an inordered list of animals to test it on:
 
bird cat crab dog elephant fly horse porcupine rabbit monkey

But if I use the code to find the predecessor of crab for eg, it will say nothing is there. I'm a little confused behind the logic of Predecessor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

BTNode * treeMaximum (BTNode * root) {
	if (root == NULL)
		return NULL;
		
	while (root->right != NULL)
		root = root->right;
	
	return root;
}

  BTNode * inOrderPredecessor (BTNode * node) {	
	if(node==NULL)
		return NULL;
		
	if(node->left!=NULL)
		return treeMaximum(node->left);
		
	BTNode *parent;
	parent=NULL;
	
	while(parent!=NULL && node==parent->left){
		parent=node;
		parent=parent->parent;
	}	
	return parent;
}
You're pretty close.

1
2
3
4
5
6
7
8
9
BTNode* inOrderPredecessor(BTNode* node) {
    if (!node)
        return nullptr;
    if (node->left)
        return treeMaximum(node->left);
    while (node->parent && node == node->parent->left)
        node = node->parent;
    return node->parent;
}

Last edited on
Topic archived. No new replies allowed.