Is There A Better Solution?
While this solution was pretty straightforward, there is much room for improvement. The complexity of the above solution is O(N), where N is the number of nodes in the tree. Since it's a traversal challenge and we have to visit each node, this makes sense.
However, the space complexity here is also O(N) since the stack will eventually hold all nodes. If the tree has a long height, the stack could manage thousands of nodes simultaneously. Hence, we can try to improve this complexity.
A better approach (called Morris Traveral) uses recursion to solve the problem efficiently. It also uses the fact that we can save references to nodes in the Node object's attributes: Node rightNode and Node leftNode as shown above.
When we start from a certain node A, we try to find the rightmost leaf node of its left and right subtrees. Once we reach this leaf node, we see its right node stores null. We can use this pointer to store the address of the ancestor node A:
