The standard least common ancestor problem ....
but with a constraint that the tree is not a BST ... its a Binary tree .. No parent pointer ...
Get Preorder, InOrder and PostOrder of the tree.
Then follow the steps to get the LCA of the two nodes n1 and n2.
1. S1 = {List of nodes from Preorder that fall before n1 and n2}
2. S2 = {List of nodes from Inorder that fall are between n1 and n2}
3. S3 = {List of nodes from Postorder that fall after n1 and n2}
LCA of n1 and n2 = Intersection(S1, S2, S3)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment