Find parent of given node in a Binary Tree with given postorder traversal | C ++ implementation to find the parent of the given node K in a binary tree whose post - order traversal is N natural numbers ; Function to find the parent of the given node ; Condition to check whether the given node is a root node . if it is then return - 1 because root node has no parent ; Loop till we found the given node ; Finding the middle node of the tree because at every level tree parent is divided into two halves ; if the node is found return the parent always the child nodes of every node is node / 2 or ( node - 1 ) ; if the node to be found is greater than the mid search for left subtree else search in right subtree ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findParent ( int height , int node ) { int start = 1 ; int end = pow ( 2 , height ) - 1 ; if ( end == node ) return -1 ; while ( node >= 1 ) { end = end - 1 ; int mid = start + ( end - start ) / 2 ; if ( mid == node end == node ) { return ( end + 1 ) ; } else if ( node < mid ) { end = mid ; } else { start = mid ; } } } int main ( ) { int height = 4 ; int node = 6 ; int k = findParent ( height , node ) ; cout << k ; return 0 ; }