/* Lowest Common Ancestor in a tree in O(1) memory Description Given a binary tree (not a search tree): struct Node { Node* parent; Node* left; Node* right; } Write a function that, for two given nodes, returns their lowest (nearest) common ancestor: Node* Lca (Node* a, Node* b); */

To find the Lowest Common Ancestor (LCA) in a binary tree with parent pointers and without additional memory, you can use the following approach:

1. Calculate the depth of each of the two nodes.
2. Raise the deeper node up the parent chain until both nodes are at the same depth.
3. Then, move both nodes up the parent chain simultaneously until they meet — that node will be the LCA.

Example in Go:

Type Node struct {
    parent *Node
    left   *Node
    right  *Node
}

func depth(n *Node) int {
    d := 0
    for n != nil {
        n = n.parent
        d++
    }
    return d
}

func Lca(a, b *Node) *Node {
    da := depth(a)
    db := depth(b)

    // Raise the deeper node
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Move up together until a common ancestor is found
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

This algorithm uses only pointers and constant memory, operating in O(h) time, where h is the height of the tree.