Given a binary tree and a node in the binary tree, find Postorder successor of the given node.
Examples: Consider the following binary tree 20 / \ 10 26 / \ / \ 4 18 24 27 / \ 14 19 / \ 13 15 Postorder traversal of given tree is 4, 13, 15, 14, 19, 18, 10, 24, 27, 26, 20. Input : Complexity Analysis:24 Output : 27 Input : 4 Output : 13
A simple solution is to first store Postorder traversal of the given tree in an array then linearly search given node and print node next to it.
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space : O(n)
An efficient solution is based on below observations.
- If given node is root then postorder successor is NULL, since root is the last node print in a postorder traversal
- If given node is right child of parent or right child of parent is NULL, then parent is postorder successor.
- If given node is left child of parent and right child of parent is not NULL, then postorder successor is the leftmost node of parent’s right subtree
Implementation:
C++
// CPP program to find postorder successor of // given node. #include <iostream> using namespace std; struct Node { struct Node *left, *right, *parent; int value; }; // Utility function to create a new node with // given value. struct Node* newNode( int value) { Node* temp = new Node; temp->left = temp->right = temp->parent = NULL; temp->value = value; return temp; } Node* postorderSuccessor(Node* root, Node* n) { // Root has no successor in postorder // traversal if (n == root) return NULL; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. Node* parent = n->parent; if (parent->right == NULL || parent->right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. Node* curr = parent->right; while (curr->left != NULL) curr = curr->left; return curr; } // Driver code int main() { struct Node* root = newNode(20); root->parent = NULL; root->left = newNode(10); root->left->parent = root; root->left->left = newNode(4); root->left->left->parent = root->left; root->left->right = newNode(18); root->left->right->parent = root->left; root->right = newNode(26); root->right->parent = root; root->right->left = newNode(24); root->right->left->parent = root->right; root->right->right = newNode(27); root->right->right->parent = root->right; root->left->right->left = newNode(14); root->left->right->left->parent = root->left->right; root->left->right->left->left = newNode(13); root->left->right->left->left->parent = root->left->right->left; root->left->right->left->right = newNode(15); root->left->right->left->right->parent = root->left->right->left; root->left->right->right = newNode(19); root->left->right->right->parent = root->left->right; struct Node* res = postorderSuccessor(root, root->left->right->right); if (res) printf ( "Postorder successor of %d is %d\n" , root->left->right->right->value, res->value); else printf ( "Postorder successor of %d is NULL\n" , root->left->right->right->value); return 0; } |
Java
// Java program to find postorder successor of // given node. import java.util.*; class GfG { static class Node { Node left, right, parent; int value; } // Utility function to create a new node with // given value. static Node newNode( int value) { Node temp = new Node(); temp.left = null ; temp.right = null ; temp.parent = null ; temp.value = value; return temp; } static Node postorderSuccessor(Node root, Node n) { // Root has no successor in postorder // traversal if (n == root) return null ; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. Node parent = n.parent; if (parent.right == null || parent.right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. Node curr = parent.right; while (curr.left != null ) curr = curr.left; return curr; } // Driver code public static void main(String[] args) { Node root = newNode( 20 ); root.parent = null ; root.left = newNode( 10 ); root.left.parent = root; root.left.left = newNode( 4 ); root.left.left.parent = root.left; root.left.right = newNode( 18 ); root.left.right.parent = root.left; root.right = newNode( 26 ); root.right.parent = root; root.right.left = newNode( 24 ); root.right.left.parent = root.right; root.right.right = newNode( 27 ); root.right.right.parent = root.right; root.left.right.left = newNode( 14 ); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode( 13 ); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode( 15 ); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode( 19 ); root.left.right.right.parent = root.left.right; Node res = postorderSuccessor(root, root.left.right.right); if (res != null ) System.out.println( "Postorder successor of " + root.left.right.right.value + " is " + res.value); else System.out.println( "Postorder successor of " + root.left.right.right.value + " is NULL" ); } } |
Python3
""" Python3 program to find postorder successor of a node in Binary Tree.""" # A Binary Tree Node # Utility function to create a new tree node class newNode: # Constructor to create a new node def __init__( self , data): self .value = data self .left = None self .right = None self .parent = None def postorderSuccessor(root, n) : # Root has no successor in postorder # traversal if (n = = root): return None # If given node is right child of its # parent or parent's right is empty, # then parent is postorder successor. parent = n.parent if (parent.right = = None or parent.right = = n): return parent # In all other cases, find the leftmost # child in right subtree of parent. curr = parent.right while (curr.left ! = None ): curr = curr.left return curr # Driver Code if __name__ = = '__main__' : root = newNode( 20 ) root.parent = None root.left = newNode( 10 ) root.left.parent = root root.left.left = newNode( 4 ) root.left.left.parent = root.left root.left.right = newNode( 18 ) root.left.right.parent = root.left root.right = newNode( 26 ) root.right.parent = root root.right.left = newNode( 24 ) root.right.left.parent = root.right root.right.right = newNode( 27 ) root.right.right.parent = root.right root.left.right.left = newNode( 14 ) root.left.right.left.parent = root.left.right root.left.right.left.left = newNode( 13 ) root.left.right.left.left.parent = root.left.right.left root.left.right.left.right = newNode( 15 ) root.left.right.left.right.parent = root.left.right.left root.left.right.right = newNode( 19 ) root.left.right.right.parent = root.left.right res = postorderSuccessor(root, root.left.right.right) if (res) : print ( "postorder successor of" , root.left.right.right.value, "is" , res.value) else : print ( "postorder successor of" , root.left.right.right.value, "is None" ) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find postorder successor of // given node. using System; class GfG { class Node { public Node left, right, parent; public int value; } // Utility function to create // a new node with given value. static Node newNode( int value) { Node temp = new Node(); temp.left = null ; temp.right = null ; temp.parent = null ; temp.value = value; return temp; } static Node postorderSuccessor(Node root, Node n) { // Root has no successor in // postorder traversal if (n == root) return null ; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. Node parent = n.parent; if (parent.right == null || parent.right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. Node curr = parent.right; while (curr.left != null ) curr = curr.left; return curr; } // Driver code public static void Main(String[] args) { Node root = newNode(20); root.parent = null ; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; Node res = postorderSuccessor(root, root.left.right.right); if (res != null ) Console.WriteLine( "Postorder successor of " + root.left.right.right.value + " is " + res.value); else Console.WriteLine( "Postorder successor of " + root.left.right.right.value + " is NULL" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript program to find postorder successor of // given node. class Node { constructor() { this .value = 0; this .left = null ; this .right = null ; this .parent = null ; } } // Utility function to create // a new node with given value. function newNode(value) { var temp = new Node(); temp.left = null ; temp.right = null ; temp.parent = null ; temp.value = value; return temp; } function postorderSuccessor(root, n) { // Root has no successor in // postorder traversal if (n == root) return null ; // If given node is right child of its // parent or parent's right is empty, then // parent is postorder successor. var parent = n.parent; if (parent.right == null || parent.right == n) return parent; // In all other cases, find the leftmost // child in right subtree of parent. var curr = parent.right; while (curr.left != null ) curr = curr.left; return curr; } // Driver code var root = newNode(20); root.parent = null ; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; var res = postorderSuccessor(root, root.left.right.right); if (res != null ) document.write( "Postorder successor of " + root.left.right.right.value + " is " + res.value); else document.write( "Postorder successor of " + root.left.right.right.value + " is NULL" ); // This code is contributed by famously. </script> |
Postorder successor of 19 is 18
Complexity Analysis:
- Time Complexity : O(h) where h is height of given Binary Tree.
- Auxiliary Space : O(1) since no use of arrays, stacks, queues.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!