CODEWITHSUNDEEP
binary-search-tree
karma
karma

Reputation: 137

What will be the successor of a right child node x when: "the first ancestor of X do fall in the left subtree"

I am a little confused on finding a successor for one particular node, that is where a node x is the right child(no child nodes of x exists) and it's parent is a left child of the root node. In such a case what will be the successor of node x.

What will be the successor of the left sub tree's node 76? I read many other tutorials as well with no success. Most tutorial talks about cases on nodes such as 19 where it's successor is 23 and node 23 where it's successor is 50. Or the successor of 76 is 72/50 For the right child we have this condition X is a right child of its parent P Then the first ancestor of X, lets call it A, such that X falls in the left subtree of A is the successor of X. Thanks.

Upvotes: 0

Views: 466

Answers (1)

shani klein
shani klein

Reputation: 344

Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal. So the Successor of 76 is no one , or NULL if you would like .

you can also look at it as the node with the smallest key greater than the key of input node. So, there is no node that greater that 76 , again - by this definition, the Successor of 76 is NUll.

Upvotes: 0

Related Questions