Find right sibling of a binary tree with parent pointers | A class to create a new Binary Tree Node ; Method to find right sibling ; GET Parent pointer whose right child is not a parent or itself of this node . There might be case when parent has no right child , but , current node is left child of the parent ( second condition is for that ) . ; Move to the required child , where right sibling can be present ; find right sibling in the given subtree ( from current node ) , when level will be 0 ; Iterate through subtree ; if no child are there , we cannot have right sibling in this path ; This is the case when we reach 9 node in the tree , where we need to again recursively find the right sibling ; Driver Code ; passing 10
class newNode : NEW_LINE INDENT def __init__ ( self , item , parent ) : NEW_LINE INDENT self . data = item NEW_LINE self . left = self . right = None NEW_LINE self . parent = parent NEW_LINE DEDENT DEDENT def findRightSibling ( node , level ) : NEW_LINE INDENT if ( node == None or node . parent == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT while ( node . parent . right == node or ( node . parent . right == None and node . parent . left == node ) ) : NEW_LINE INDENT if ( node . parent == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT node = node . parent NEW_LINE level -= 1 NEW_LINE DEDENT node = node . parent . right NEW_LINE while ( level < 0 ) : NEW_LINE INDENT if ( node . left != None ) : NEW_LINE INDENT node = node . left NEW_LINE DEDENT elif ( node . right != None ) : NEW_LINE INDENT node = node . right NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT level += 1 NEW_LINE DEDENT if ( level == 0 ) : NEW_LINE INDENT return node NEW_LINE DEDENT return findRightSibling ( node , level ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 , None ) NEW_LINE root . left = newNode ( 2 , root ) NEW_LINE root . right = newNode ( 3 , root ) NEW_LINE root . left . left = newNode ( 4 , root . left ) NEW_LINE root . left . right = newNode ( 6 , root . left ) NEW_LINE root . left . left . left = newNode ( 7 , root . left . left ) NEW_LINE root . left . left . left . left = newNode ( 10 , root . left . left . left ) NEW_LINE root . left . right . right = newNode ( 9 , root . left . right ) NEW_LINE root . right . right = newNode ( 5 , root . right ) NEW_LINE root . right . right . right = newNode ( 8 , root . right . right ) NEW_LINE root . right . right . right . right = newNode ( 12 , root . right . right . right ) NEW_LINE res = findRightSibling ( root . left . left . left . left , 0 ) NEW_LINE if ( res == None ) : NEW_LINE INDENT print ( " No ▁ right ▁ sibling " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( res . data ) NEW_LINE DEDENT DEDENT