Find parent of given node in a Binary Tree with given postorder traversal | Python implementation to find the parent of the given node ; Function to find the parent of the given node ; 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 ; Find 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
import math NEW_LINE def findParent ( height , node ) : NEW_LINE INDENT start = 1 NEW_LINE end = pow ( 2 , height ) - 1 NEW_LINE if ( end == node ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT while ( node >= 1 ) : NEW_LINE INDENT end = end - 1 NEW_LINE mid = start + ( end - start ) // 2 NEW_LINE if ( mid == node or end == node ) : NEW_LINE INDENT return ( end + 1 ) NEW_LINE DEDENT elif ( node < mid ) : NEW_LINE INDENT end = mid NEW_LINE DEDENT else : NEW_LINE INDENT start = mid NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT height = 4 NEW_LINE node = 6 NEW_LINE k = findParent ( height , node ) NEW_LINE print ( k ) NEW_LINE DEDENT