inorder predecessor and inorder successor in binary tree and binary search tree-MyCodeVillage

Topic of focus :

• what is  a binary tree ?
• what is a binary search tree?
• what is inorder traversal in binary tree ?
• what is inorder predecessor and inorder successor ?
• how to find inorder predecessor and inorder successor?

what is a binary tree ?

       A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

The above figure is a example of binary tree . every node has two children , for example

2 has left child 4 and right child 10. 

A Binary Tree node contains following parts.

1. Data
2. Pointer to left child
3. Pointer to right child  

what is a binary search tree?

  

 Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.

The left and right subtree each must also be a binary search tree.

some key points to remember about binary search tree are :

• all nodes have unique key value .
• inorder traversal of binary search tree gives sorted array .

what is inorder traversal  in binary tree ?

  

Process all nodes of a tree by recursively  processing the left subtree, then processing the  root , and finally the right subtree.

Also known as symmetric traversal. 

Lets consider the above binary tree , inorder traversal of tree is :

1, 3, 4, 6, 7, 8 , 10 , 13 , 14 

Recommended post : short and quick methord to find preorder , inorder  and postorder traversal in a binary tree 

what is inorder predecessor and inorder successor ?

first , what you should know is inorder predecessor and inorder successor are calculated with respect to a node in a binary tree .

for e.g inorder predecessor of 3 is 1 and inorder successor of 3 is 4 .

not understand ?

ok , let me explain ..

      inorder predecessor of a node in a binary tree  is the element which comes before that node while doing inorder traversal .

       similarly , inorder successor of a node in  a binary tree is the element which comes after that node while doing inorder traversal.

how to find inorder predecessor and inorder successor?

There are two methords : 

     first is , find the inorder traversal and then find the corresponding inorder sucessor and inorder predecessor for any node you want .

    Second is , you can find inorder successor and predecessor  by simply focusing on the binary tree.

what does it mean ?

       Inorder predecessor of a node in a binary tree is the node which is the right -most member (if present )of the left subtree of that node .

   

       similarly , inorder successor of a node in a binary tree is the node which is the left-most child(if present ) of the right subtree of that node .

                

                        

  what is inorder predecessor of 8 ?

 solution : left subtree  of 8 is 

   right most child of this left subtree is 7.

so inorder predecessor of 8  is 7.

THank you

write in comment if you stuck somewhere.